「持续更新」Everyday DS

Arghariza · 2023-09-08 10:29:34 · 算法·理论

https://www.cnblogs.com/Ender32k/p/17686877.html

Day 1 CF1270H Number of Components

发现极大的连通块形如 [l,r] 区间形式，其中满足 \min\limits_{k=1}^{l-1}a_{k}>\max\limits_{k=l}^ra_k，而且 \min\limits_{k=l}^ra_k>\max\limits_{k=r+1}^na_k。

所以区间 [l,r] 的右端点满足 \min\limits_{k=1}^ra_k>\max\limits_{k=r+1}^na_k。将 \ge a_r 标 1，<a_r 标 0，那么序列形如 111\cdots 100\cdots 0 的形式（前面一共有 r 个 1）。这是充要条件。

由于数列的数互不相同，所以可以尝试枚举 a_r=v，合法的 r 个数即满足序列形如 111\cdots 100\cdots 0 的 v 的个数，即满足 01 序列中只有一对相邻形如 10 的串的序列的个数，这对相邻的 10 对应唯一的 (a_r,a_{r+1})。

所以对于一对 (a_i,a_{i+1})，满足其在 01 序列中形成形如 10 串的 v 满足 v\in [\min(a_i,a_{i+1}),\max(a_i,a_{i+1}))。所以我们给区间 [\min(a_i,a_{i+1}),\max(a_i,a_{i+1})) 上的数全部 +1，表示这对 (a_i,a_{i+1}) 会给这段区间的 v 的 01 序列贡献一个 10。

最后我们需要求出 10 个数为 1 的序列的个数。考虑到离散化后对于所有的 v，其 01 序列中至少都会有一对 10，直接维护最小值以及最小值个数即可。

Day 2 Ynoi2015 我回来了

介绍个最劣解 O(m\sqrt n+n\sqrt n+n\alpha(n)\ln n) 做法。

首先令 b_i\gets a_i-1，区间 [l,r] 的答案就是：

考虑如何动态维护后面那个式子。我们对每一个 k\in [1,n] 维护一个大小 n/k 的 bitset，代表所有 b_i/k 的值，最低位的 0 就是 k 对应的 \text{mex}。

加入一个 b_i 的时候考虑所有 b_i/k 的值，不难发现只有 O(\sqrt n) 种取值，于是可以分成 O(\sqrt n) 个区间修改，每次修改形如 (l,r,x)，代表往 l 到 r 每个 bitset 中插入数 x。

因为 n 个 bitset 的总大小不超过 n\ln n（调和级数），所以如果我们每次修改 (l,r,x) 都能找到一个是 0 的位，把这位换成 1，并不访问别的 1 的话，这个复杂度就是正确的。于是不难想到对每个 x 维护一个并查集，这样就可以从一个位置 p\in[l,r] 迅速跳到下一个第 x 位为 0 的 p' 了。

然后我们在跳 p 的时候需要动态维护 p 的 bitset 的 \text{mex}，由于只有插入没有删除，这显然可以均摊 O(n\ln n) 维护。得到这个 p 的权值后，就只需要一个单点修改 O(1) 的数据结构来维护 m 次区间和查询了。显然分块可以做到 O(1)-O(\sqrt n)。于是就得到了 O(m\sqrt n+n\sqrt n+n\alpha(n)\log n) 的优秀做法。

Day 3 BalticOI 2020 小丑

整体二分。

有个小技巧，就是可以把存边的数组往后复制一遍，然后删去区间 [l,r] 就相当于保留区间 [r+1,l+m-1] 的边。于是只需要解决这么个问题：

给定一张 n 个点 m 条边的无向图，q 次询问，每次只保留区间 [l,r] 的边，问是否是二分图。

乍一看有点像 Cnoi2019 须臾幻境？但是其实有不用 LCT 的做法。

考虑令 f_l 表示最小的 p 使得 [l,p] 区间不是二分图。显然 f 具有单调性，即 \forall i\le i',f_i\le f_{i'}。只需要求出所有的 f_i，就可以直接根据 f_l 是否 \le r 判断是否是二分图了。

由于 f 的单调性，不难想到整体二分。令 S(l,r,v_l,v_r) 表示处理 f_{l},f_{l+1},\cdots, f_{r}，并且 v_l\le f_l\le f_r\le v_r。令 \text{mid}=\frac{l+r}{2}，于是只需要求出 f_{\text{mid}} 即可：用可撤销并查集从 \text{mid} 开始加边，第一个使得图不是二分图的位置就是 f_\text{mid}。

为了保证复杂度，需要在分治之前将 (r,v_l) 的边先加进并查集中。然后就没什么细节了。

复杂度 O(m\log m\log n+q)，整体二分复杂度写假的是小丑。

Day 4 SDOI2016 游戏

令 \text{lca}(u,v)=w，s_u 为 u 到根的距离（随便指定一个根），考虑 u\to w\to v 的路径修改：

考虑树链剖分，将修改拆分到 O(\log n) 条重链中。由于重链中 \text{id} 连续，这是关于 \text{id}(u) 的一次函数形式。李超线段树维护区间线段 \min，在区间中插入线段即可。

李超树区间插入（非全局）是 O(\log^2n) 的（分成 O(\log n) 个区间后分别再在每个区间中插入），所以复杂度是 O(n\log^3n) 的。不知道为啥能过。

Day 5 CERC2014 Pork barrel

考虑 Kruskal 算法的过程，即边权从小到大依次加入边，每条边连接两个连通块。很重要的性质是每次加入的边边权单调不降。

于是权值 [L,R] 内的边组成的最小生成树，相当于从权值为 L 的边开始跑 Kruskal，取所有 \ge L 的边组成的最小生成树，树上所有边权 \le R 的边的边权之和。

将边从小到大排序，如果对于每个边权 L，求出边权 \ge L 的一段后缀的边组成的最小生成树，就能够通过一些可持久化手段维护出此时边权 \le R 的边的边权之和。

若已经求出 L'\ge L 的最小生成树（L' 是 L 值域上的后继）T'，考虑新增 (u,v,L) 这条边，得到新的最小生成树 T：

• 若 u,v 在 T' 中联通，找到 u\to v 简单路径上边权最大的边，删去这条边，然后加入 (u,v,L)。
• 若 u,v 在 T' 中不连通，直接加入 (u,v,L)。

注意到 n\le 10^3，这允许我们在 O(nm) 的时间内求出这 m 棵最小生成树。

由于 T'\to T 的边权变化是 O(1) 的，于是只需要一个支持单点修改，区间求和的可持久化数据结构。使用可持久化权值线段树即可。

复杂度 O(nm+(m+q)\log W)。

Day 6 CF1801G A task for substrings

好神奇的题啊，我完全不会做。

建出 s_1,s_2,\cdots, s_n 的 ACAM。

考虑在 r 处统计满足条件的数对 (l,r) 的贡献。那么需要求出 f_r 表示文本串以 r 为结尾的前缀 [1,r] 中，其所有后缀中模式串的出现次数。即：