根号算法好闪，拜谢根号算法

· · 算法·理论

cnblogs

根号分治

就是利用根号平衡的思想，对于不同的数据用不同的维护方法。本质是数据分治

P8572

突然想起来了很久前做的神秘水题。O(qk) 和 O(n^2k+q) 的暴力都不难想，但是第一种在 k 大的时候会似，第二种在 n 大的时候会似。

题目保证 nk \leq 5\times 10^5，也就是说 \min(n,k) \leq \sqrt{5\times 10^5}，讨论一下 n,k 的相对大小分别用两种方法做就行了。纯纯数据分治。

CF797E

很容易想到两种暴力，一种是对于确定的 k，从后向前递推 f[i] 表示从 i 开始需要跳几次，另一种是直接每次询问暴力跳。

发现第一种的问题在于 k 太大的时候复杂度 O(nk) 会炸，第二种问题在于 k 太小的时候要跳的次数太多。

考虑根号分治，对 k \leq \sqrt{n} 的预处理答案，对于 k > \sqrt{n} 的直接跳，时间复杂度 O((n+q)\sqrt{n})。

体现了根号分治就是数据分治。

CF1039D

对于确定的 k，可以 O(n) 贪心做。

对于小的 k，直接做。对于大的 k，发现答案会比较小，枚举每个答案，二分出它对应的 k 区间。

贪心的过程类似赛道修建，都是从下向上在父节点处拼接链，但有一些区别。这题每个点只存在于一条链中，也就是要么是两个儿子的链在这里接起来，要么一个儿子连到他再向上接，可以发现第一种不劣，所以能接第一种就接第一种即可。

另外有题解提到答案不超过 \lfloor \frac{n}{k} \rfloor，而 \lfloor \frac{n}{k} \rfloor 的取值数量是根号级别的，所以答案种类数是根号级别的。不过复杂度一样。

CF1580C

每个车的周期是 x_i+y_i，看到周期，同余之类的可以想想根号分治。

考虑维护一个数组表示每天维修的车数，插入删除操作暴力区间加。可以使用差分做到 O(\frac{n}{x_i+y_i}) 修改，

对于 x_i+y_i 比较小的车，需要修改的段数太多了，但是对于周期相同的车，容易一起算。对每种周期记录周期中 \bmod (x_i+y_i) 每个余数的位置有多少车需要维修。

阈值取 \sqrt{m}，复杂度 O(m\sqrt{m})。

P5309

有一点像根号分治典题哈希冲突。

考虑修改操作与原序列分开算。

首先对于 x>\sqrt{n} ，修改的位置不会太多，直接分块维护前缀和（用分块是为了平衡修改和查询的复杂度）。

对于 x\leq \sqrt{n}，维护 \bmod x \equiv y 的位置的标记和的前缀和，修改的时候单点修改相当于前缀和的区间修改，直接暴力做，询问的时候遍历一遍所有小的循环节，可以 O(1) 算出 [l,r] 内每个余数出现的次数（细节较多，轻微卡常）。

分块

不想写，先鸽（悲

P5356

用复杂度不是很对的方法过去了。

看到数据范围，考虑到这是 Ynoi，就可以想分块了。（事实上对于 10^5 的范围，想不到好的数据结构时可以考虑分块，也许会简单一些）

设块长为 B。

对一个块内的数都加上 k，不会改变数的相对大小，可以通过打标记实现。对于散块，每次只会改 O(1) 个，暴力重构即可。修改时修改的位置之间和不修改的位置之间都保持有序，可以归并排序，因此修改复杂度 O(B+\frac{n}{B})。

查询时，考虑二分答案，散块内暴力统计，整块已经排好序，直接再二分，单次复杂度 O(\log V(B+\frac{n}{B}\log B))。

实际块长取 250 左右时跑的比较快，我也不知道为什么。

P4168

典题了属于是。即强制在线询问区间众数。

考虑分块，区间 [l,r] 的众数一定是 [l,r] 中所有整块的众数或者是在散块中出现过的数。预处理每个每个整块构成的区间的众数和每个数关于块的前缀和，询问时将整块区间众数和散块中的每个数作比较找出众数。

P3203

我一个没学过 LCT 的人都一眼 LCT，但是我不会 LCT。但是这题的分块做法非常简单！

首先会想到维护 f_i 表示从 i 会弹到哪 (f_i>i)，构成了一个树结构，每次修改相当于把一个子树整个搬走。

如果要维护每个点最终到哪，那么修改涉及到的点是 O(n) 的。如果每次暴力跳，跳的步数是 O(n) 的。于是会有一种想法，记录一个点向后跳一定范围到达的点去平衡复杂度。

显然阈值取 \sqrt n，分块，对每个块维护块内每个点跳出块到达的点，不难发现修改只与块内有关，查询最多跳块的个数次。

P3992

不难发现最优情况下，是把加油站和车分别排序后按顺序对应。但每次排序计算显然过不去，排序操作也不太好优化。

考虑转化贡献，把所有车和加油站的位置排序，得到 x 轴上 O(n) 个点。对于每个相邻两点见的线段，考虑会有多少车经过。设第 i 个点和前一个点的距离是 d_i，前 i 点中加油站个数减车数是 c_i，则答案为 \sum {|c_i|}\cdot d_i。每次修改是将一段 c_i 区间 +1 或 -1。

考虑分块。每个块块内排序，散块暴力重构，整块打标记。贡献可以写成 \sum c_i\cdot d_i - 2 \cdot \sum_{c_i<0} c_i\cdot d_i，维护一个前缀和，每次二分零点更新答案。

代码不是很好写的感觉。

P4117（CF896E）

第二分块。看起来很不对实际上是对的复杂度。

考虑分块。并查集维护值，对于散块，直接重构。对于整块，若块内最大值 mx>2x，就将 \leq x 的数加上 x，并给块打上 -x 的标记，否则直接将 >x 的数 -x。修改数都用并查集实现。

这样保证了每次会将块内值域缩小 x。势能分析法可的得复杂度是 O(V \sqrt n) 乘并查集常数的，很神奇。

莫队

CF617E & P4462

莫队板题。首先把区间异或和转为两个异或前缀和的异或，然后维护一个区间内异或前缀和值 为 i 的数个数。

P4396

莫队 + 值域分块

发现对于一些没法 O(1) 插入删除的东西，如果使用 \log 数据结构，整体复杂度就变为了 O(n\sqrt n \log n)，无法接受。

但是其实对于所有询问，修改操作有 n \sqrt n 次，但是询问操作只有 n 次，所以我们考虑继续运用根号平衡的思想，找一些 O(1) 修改，O(\sqrt n) 查询的方式，即值域分块。

但是有的时候我们有不同的需求，比如有时候二次离线需要 O(\sqrt n) 修改，O(1) 查询，此时换一种值域分块的方式，见 P5501 的二离部分，要注意区分。

P7708

较为复杂的莫队。

咕

莫队二次离线

有的时候我们没有办法 O(1) 实现插入删除，也没法值域分块（比如每次插入删除会考虑一个点对一个区间的贡献），所以我们需要把这些点对区间的贡献的询问离线下来再做，即莫队二次离线。

每一次端点移动可以看为一堆点对于一些区间的贡献，一般来说这种东西具有可减性。

记 f(i,[l,r]) 表示点 i 对 [l,r] 的贡献，假设某次移动右端点由 r 移动到 r'，贡献为

\sum_{i=r+1}^{r'} f(i,[l,i-1])=f(i,[1,i-1])-f(i,[1,l-1])

前半部分东西可以扫一遍预处理，对于后半部分，看成一段区间对一段前缀的贡献。 考虑将 g([r+1,r'],[1,l-1]) 挂到 l-1 上，然后再从前往后扫加入每个点，然后暴力回答挂在这个点上的询问，由于莫队端点移动的总长度是 O(n\sqrt n) 所以可以接受。

P5501 中二次离线部分依然不能 O(1) 处理，此时发现添加点（即修改操作）是 n 次，查询是 O(n\sqrt n) 次，此时我们需要修改根号，查询 O(1) 的数据结构。

注意：

P4887

莫队二次离线模板。

回滚莫队

有的时候我们维护的信息不支持删除，比如最大值最小值，这个时候需要一种不用删除的莫队，即回滚莫队。

回滚莫队的思想是，把左端点在一个块内的询问按右端点从左到右排序（所以不能奇偶排序优化了，悲），每次把左端点放在块尾，然后向右移动右端点，遇到询问就暴力左移左端点，询问完后再撤回，把左端点放回块尾。

看上去很暴力，但是复杂度是对的。

P5906

维护最远距离即维护区间 最大值-最小值，区间最大值最小值不可撤销。

回滚莫队，将区间分为当前块内和当前块右两块，两块内分别维护最大值和最小值。