【基础优化】分块

WeLikeStudying · 2022-03-18 08:13:56 · 算法·理论

我的基础知识……我已经不忍吐槽。
但是其实没必要啊，我终究是站在这里，带着热爱，不留遗憾的。
分块其实是一种平衡的思想，借鉴，借鉴，借鉴。
基于减小常数的目的，我们总是希望减小分块的空间开销，这也很重要。
尽管如此，限于作者的能力，这里只会收录极其简单的题目。
感谢大佬，大佬的指导，衷心祝愿其信息学之路光芒璀璨。

分块基础

例题引入：区间加，区间求和。
这题我们已经有了树状数组的解法了，但是今天我们的专题是分块，我们知道分块是对暴力的平衡，所以我们有什么办法呢。
比如说，菜鸡作者只会两种办法：
暴力维护前缀和，这样区间加需要对 O(n) 个数进行更新，但是区间求和的复杂度是 O(1) 的。
暴力维护差分数组，这样区间加需要对 O(1) 个数进行更新，但是区间求和的复杂度是 O(n) 的。（暴力二维前缀和）
那么我们能不能平衡一下呢？我们可以把 \sqrt n 个元素放到一个块内维护，每次修改会查询 O(\sqrt n) 个整块和 O(1) 个零散块。
对整块和零散块分别操作，我们得到了 O(m\sqrt n) 的复杂度。
那么分块有什么好处呢？它的复杂度似乎不如分治结构啊？第一，~~它代码短~~，第二，你会发现许多分治结构要求（亦或是强求）信息容易方便地合并（包括大段修改后的合并），但是很多时候，有些信息并不便于合并，尤其是那些不支持大段区间合并的信息，我们或许就可以使用分块进行维护。
从另外一种角度上，要想用分治结构（如线段树，平衡树）维护某些信息，相当重要的一点就是要发现它易于维护（更准确地说，是易于合并）的某些性质。

典例分析

维护数列满足：
区间加，查询区间小于 x 的数的个数。
这题如果用分治结构做怎么样？如果是单点修改就是个树套树，但对于区间修改：你需要维护少量的信息支持一个集合区间加后与另一个集合合并的结果，这似乎过于困难了。
但是使用分块结构是不是更简单一点呢？
由于层数很低，我们分块可以直接保存块内数组排序后的情况，区间加的时候对于整块可以打一个标记，然后查询的时候二分，而对于零散的块，我们直接重构即可。
设块长为 B，区间加的时候：整块 O(1)，零散块 O(B)（重构的时候当然是归并排序）。
区间查询的时候，整块 O(\log B)，零散块 O(B)。
取 B=O(\sqrt{n\log n})，我们得到了一个较优的复杂度：O(m\sqrt{n\log n})。

例题 1

例题 1。
支持区间加，区间第 k 小。
如果直接套用上面的做法，复杂度是 O(m\sqrt{n\log n}\log n)，会被毒瘤卡。
我们分析一下，查询复杂度乘了 \log n，这十分恶心，整块的优化显然较为困难，考虑零散块：
这里是一个十分有趣的操作：我们可以在 O(B) 的时间得到零散块的数的顺序排列，然后就可以在 O(B) 的时间内将他们归并为一个新的整块然后在这个整块上二分，所以零散块的查询复杂度变成 O(B) 了。
我们选择 B=O(\sqrt n\log n)，所以最终复杂度即为 O(m\sqrt n\log n)，应该可以通过此题。
这给我们的启示是分块也利用信息。（只不过要求没有那么高而已）
还有一个启示是 \text{STL} 真好用。
代码，对零散块的处理有点细节，还差点越界，一开始有点被卡，调小了一点块长过了，用多序列二分还可以进一步优化复杂度。

根号平衡

根号还有另一个作用，在操作不平衡的时候实现复杂度的平衡，下面是一些简单的练习：
维护数列：
维护一个值域为 O(n) 的集合：

例题 2

例题 2。
有一个数列，一些区间查询，有两个操作：对数列进行修改，求一个区间的查询的和。
查询相对静态，可以试着对查询进行分块，首先我们维护原数列的区间和，其次我们分块维护每一块内现有的答案和和数列上每个位置的贡献，修改的时候暴力修改，查询的时候对 O(\sqrt m) 个散块查询的复杂度比较要紧。
所以你也明白了，修改和查询的复杂度不够平衡，用分块维护，复杂度即 O(q\sqrt n+q\sqrt m)，这很有趣，因为空间的问题还是比较突出的，代码实现。
数组下标开错很离谱，开无符号长整型过更加离谱！

例题 3

例题 3。
支持区间加，查询数列中的某个数在过去的多少时刻不小于 y。
直接对数列分块？感觉并没有效果？尝试离线？我的头脑中出现了一个矩形……
所以问题变成我们熟悉的老朋友了，我们用朴素的分块就可以在 O(m\sqrt{n\log n}) 的时间解决它。
我们通过维度的转换，将问题变成我们熟悉的问题，这种技巧真的太神奇了！代码实现。

普通莫队

通常莫队用来维护这样一类子集的信息：支持 O(f(n)) 插入一个元素，O(g(n)) 删除一个元素，且无法比暴力更高效地合并元素。
我们需要处理的就是给出一个点集，多次询问这个子集的信息。
特殊的情况即区间信息的维护，下面的分析省略 f(n) 和 g(n)。
假设序列长度为 n，有两个区间询问 [l_1,r_1] 和 [l_2,r_2]，那么我们可以用 |l_2-l_1|+|r_1-r_2| 的复杂度从一个区间转移到另一个区间。
那么我们如果可以快速地求出 (l_i,r_i) 这 m 个点的平面曼哈顿距离最小斯坦纳树，我们就可以到达用这种做法的理论最优情况，事实上，我们可以在 O(n\log n) 的时间内求出 n 个点的曼哈顿距离最小生成树，从而达到与最小斯坦纳树同阶的情况。
但是另一种更为简单的方法可以达到这个东西在最坏情况下的渐进时间界 n\sqrt m。
设块长为 B，将区间按以左端点所在块的编号（小到大）为第一关键字，以右端点为第二关键字排序，然后暴力这样跳。
左端点的移动量最大是 mB，右端点则为 \dfrac {n^2}B，设 B=O(\dfrac n{\sqrt m})，得到理论最优复杂度 n\sqrt m。
下面是一些简单的卡常方法：
调节块长（注意可能会被边界数据卡）。
奇偶化排序：属于奇数块的地方 r 从小到大排序，属于偶数块的地方 r 从大到小排序，可以优化 r 指针的移动次数。

例题 4

例题 4。
查询区间内每个数的出现次数的平方和。
如果使用其它做法会面临贡献过于多样的问题。
但是用莫队做很简单，开个桶维护，改变的贡献容易 O(1) 计算，于是愉快地水过此题，代码实现。

例题 5

例题 5。
给定一个 n 个点的树，每个节点有一个颜色，支持换根和查询 x 的子树和 y 的子树中节点颜色相同的方案数。
尝试做 \text{dfs} 序方面的转换，那么换根会有什么变化？如果节点在子树外，子树代表的区间不变，如果节点就是根，是整个区间，否则是整个区间减去节点的次级子树。
我们可以快速地把它搞成一堆序列询问，然后我们发现它具有可差分性，然后我们就把它搞成一堆前缀询问，这个可以用莫队来维护和更新。
一个小问题是拆出来的询问有点太多了（一次可以拆 9 个），可以考虑使用基数排序，复杂度可以降下来，~~由于莫队太快排序反而成为瓶颈了吗。~~
代码实现。

例题 6

例题 6。
静态查询区间出现次数第 k_1 小的数内第 k_2 小的数。
暴力上莫队，然后问题变成如何高效地更新。
更具体化地，问题变成了如何高效维护 O(n\sqrt m) 个插入删除操作和 O(m) 个对出现次数第 k_1 小的数内第 k_2 小的数的全局查询。
我们用之前的 O(\sqrt n) 查询的根号平衡数据结构即可维护，复杂度 O(n\sqrt m +m\sqrt n)~~莫队套分块~~。
不过实现有一个小细节：这题卡空间，有个很有趣的事情，如果一个数 x 出现了 y 次，我们在 1 到 y 的桶内都更新 x，在桶内部离散化，保证了线性的空间复杂度，代码。
这其实是一种常见的启发性思路，用莫队简化问题并带来不平衡的询问，此时再套一个分块数据结构，往往不会对复杂度有什么显著影响。

例题 7

例题 7。
众所周知这题可以用回滚莫队做，但是今天我们尝试用值域分块来做！
等等那么这样就没啥好讲的了，和上一题一样了，只不过数据还要经过预先的离散化而已，代码就咕咕，因为并没有什么困难的地方(^_^)。

例题 8

例题 8。
每次查询一个区间子序列去重后的和，每次询问的模数都不同。
如果模数一开始就给定，我们可以直接上莫队（尽管需要对作者来说十分复杂的组合计数），但是模数每次不一样。
咱们总不能对模数下手吧，我们的目标就是每次利用信息在根号时间内直接计算答案。
咱们尝试通过贡献而非更新入手计算，让我们计算一个（单独的）元素对答案的贡献，假设区间长度为 L，这个元素在该区间出现了 c 次，那么总的贡献就是 x(2^L-2^{L-c})。（总的贡献减去没有出现的子序列）
你尝试化简这个式子然而没有效果，最后突然发现有个出现次数的性质：出现次数小于 \sqrt n 的，出现次数本身就是性质，出现次数大于 \sqrt n 的，一定不超过 \sqrt n 个。
好的因此我们把出现次数大于 \sqrt n 的标记一遍，出现次数小于 \sqrt n 的也可以在莫队的时候装在桶里，当我们查询的时候，我们查询完出现次数小于 \sqrt n 的贡献的时候，再找一遍出现次数大于 \sqrt n 的数即可。
接下来，瓶颈在于查询时候的快速幂，调节分治的上下界我们就得到了 O(m\sqrt{n\log n}) 的奇怪做法。
不过注意到我们查询的时候有宽松的 O(\sqrt n) 的时间，我们可以顺便处理 2 的 \sqrt n 次幂，所以总的复杂度是 O(n\sqrt n+m\sqrt n)。
代码实现，卡常的核心是优化取模次数，现在想来很后怕，看来 \log^{0.5} 真的会被卡。
简单来说，如果把数量相同的元素看成一块，我们自然形成了 O(\sqrt n) 块，即自然根号。

例题 9

例题 9。
这个比较简单，转化以下，小 \text{Z} 的袜子可以处理 p 不是 10 的因子的情况。
接下来问题是 p\in\{2,5\} 的情况，你会发现它只取决于尾数，所以问题变得更简单了，所以这么简单，我就咕掉代码(#`O′)。

区间众数问题

给出一个数列，静态查询一个区间的众数的出现次数。
由于莫队转移时答案最多会加一或者减一，可以直接维护，代码。

例题 10

例题 10。
静态查询区间内，有多少个子区间满足最多只有一个出现次数为奇数的数o(￣▽￣)ブ。
感觉很妙，一开始没有想到。
还是如何维护莫队的问题，感觉没什么思路，但是出现次数是可差分的，所以差分下，就变成了在区间内部选择两个点，然后它们最多有一个位置相差 1。
压位就变成了相差 2^k，暴力离散化，插入删除的时候暴力做，复杂度是 O(|\Sigma|n\sqrt m)。
代码实现。

区间逆序对问题

可以莫队做，普通莫队查询前驱后继要带 \log 的树状数组的，代码实现，但是模板题卡该做法。
然后你把询问拆出来，我们要快速查询大于或小于某个数的个数，插入和查询都是 O(n\sqrt m) 级别，看样子十分平衡，不好优化。
有一个很暴力的做法就是用主席树维护询问，时间复杂度相同但是空间明显增长，常数较大。
可持久化的好处是跑莫队的时候不需要插入，带来了插入和查询的不平衡，所以一个更有趣的做法是可持久化块状树，我们容易让它支持 O(\sqrt n) 的可持久化插入和 O(1) 的查询，然后复杂度就被优化到 O(n\sqrt n+n\sqrt m)，但常数奇大无比，与树状数组自带的小常数形成鲜明的对比，而且空间复杂度巨大，绝对连树状数组都跑不过。
不过我们发现主席树的本质不就是差分呗，我们查询的信息本身就有差分性，可以直接差分，也就是把莫队的整个过程要算的贡献用离线下来，算出来之后塞回去，这样就只有前缀查询了，然后询问与数列长度不平衡，可以跑值域分块，然后复杂度也是一样的，但是由于要将莫队的整个过程离线下来，空间复杂度还是相当巨大(｡･∀･)ﾉﾞ。
(╯▔皿▔)╯接下来怎么办？(⊙﹏⊙)我们猛然发现我们似乎没有必要用 O(n\sqrt m) 的过程来定义一个莫队的状态转移，实际上可以用一个 O(m) 的状态来表示莫队，因为莫队的很多状态都是连续的！(ˇ∀ˇ)
将莫队一段连续的端点移动差分之后，容易发现它们被统一为两类问题。
点随段动：即查询一个点有多少的前缀小于它，这个显然可以 O(n\log n) 预处理，然后通过前缀和可以支持区间查询。
点动段不动：[l,r] 区间内的点在 [1,x] 的贡献（注意由于外层套了莫队，即使我们枚举所有的点暴力，我们也只需要枚举 O(n\sqrt m) 个点），可以说很明确了，和之前的离线做法相同，仍然出现了询问与数列长度的不平衡，需要用值域分块来维护，时间复杂度 O(n\sqrt n+n\sqrt m)，空间复杂度 O(m+n)，代码实现。
它带来的启发就是如果莫队维护的信息具有差分性，虽然插入和查询没有不平衡，但将整个过程离线下来（利用差分性把插入变成 O(n) 级别），却出现了插入和查询的不平衡，从而可以更好地优化复杂度。
通常情况下，将莫队的 O(m) 个转移点，而不是 O(n\sqrt m) 个操作离线下来，可以取得好得多的效果。

树上莫队

如果是子树信息允许离线可以直接启发式合并，不需要莫队。
如果是链信息怎么做？直接在括号序上跑莫队即可，左括号代表入栈右括号代表出栈。
缺点是括号序方法不支持回滚。

带修莫队

利用三维信息排序转移，仍然可以得到 O(n^{5/3}) 的复杂度。
排序方法就是以第一个，第二个端点所在块的大小为第二关键字，以第三个端点为第三关键字，跑莫队，取块长为 O(n^{2/3})，块大一点会比较优秀。
至于与询问个数 m 有关的最优块长 B 是什么？众说纷纭，个人认为最严谨的回答：
但是实际分块个人采用 B=O(n/m^{1/3})，大胆猜想得到 O(nm^{2/3}) 的复杂度。
其实就是高维莫队，但是维度稍微高一点莫队就没有优势了，~~无优势论~~。

回滚莫队

利用加入删除复杂度的不平衡来优化莫队的实现。
自己手玩大概就可以理解它具体的实现，这里不过多说明(￣▽￣)"。

例题 11

例题 11。
求区间差的最小值，虽然正解是两个 \log 但是只要莫队优化复杂度也可以过，经验。
传统的做法需要维护前驱后继，显然不可过，发现链表可以处理只删除的情况，我们用值域分块维护 O(1) 插入删除和 O(\sqrt w) 的查询最小值，即可做到 O(n\sqrt m+m\sqrt w)，等等这题 w 好巨大……
可以利用 \text{bitset}，查询部分自带极小常数，O(n\sqrt m+\frac{m\sqrt w}{32}) 大概率可以卡过，空间复杂度 O(n+w)，因为要维护可重集没有办法卡空间。
但是利用 \text{bitset} 可以实现快速地插入删除和查找前驱后继的性质，仍然可以胡出一个较快的算法，但这里只留下蒟蒻思考的痕迹(；′⌒`)。
~~问题是只加会被卡复杂度，所以强行转只删然后值域过大还是被卡。~~

例题 12

例题 12。
这个比那题清晰很多，维护相同的数的双端队列，我们就可以用回滚莫队来维护只有增加的情况，代码实现。

例题 13

例题 13。
区间查询最长值域连续段的长度，同样可以用回滚莫队直接维护只有增加的情况，需要维护每个连续段左端和右端的端点，代码。

例题 14

例题 14。
查询区间 [l,r] 有多少非空子区间在值域 [x,y] 内。
观察发现，合法的情况一定是一堆不相交连续段的一些子区间，很自然地想到这个问题既然不好做，就二维变换下。
新的问题是查询区间 [x,y] 形成了多少个 [l,r] 之间的值域连续段，这个问题稍微好做一些，我们尝试用分块维护合并，即维护块内块内的值域连续段的平方和与块头和块尾的值域连续段长度，接下来问题就在于修改操作。
然后实际操作的时候发现即使不维护最大值，删除仍然出现了一点困难，使用回滚莫队维护，可以参照例题 13 的具体实现，没有它我不容易想到这一层，代码，常数较大。
它给我们的启示就是线段树可以快速维护可以 O(1) 合并的信息，但是我们为了根号平衡可以强行把它改成 O(1) 修改，O(\sqrt n) 查询的块状树，实现根号平衡的目的。

再谈分块

你想过没有，如果那些用莫队随便搞的东西全部加上强制在线，该怎么办。
虽然有相关算法，但这样的莫队或许很难支持稍微复杂一点的操作~~而且思想很像分块你不觉得吗~~。
然后你甚至都需要跑莫队了，你还想有更快的做法？但是你不甘于暴力！最后还是绕回分块。

再谈区间众数

强制在线。
假如我们先维护每块之间的区间众数，在查询的时候我们只需要考虑散块的额外贡献，即查询 O(\sqrt n) 个数的区间出现次数然后取较大值。
对于查询，我们用动态开点/可持久化线段树优化，时间复杂度是 O(n\log n+m\sqrt n\log n)，空间复杂度 O(n\log n)。
我们用动态开点/可持久化块状树维护，时间复杂度 O((n+m)\sqrt n)，空间复杂度 O(n\sqrt n)。
但是可持久化块状树这种东西，估计也就我借鉴的那位大佬会把它出成题目……有没有更简单，而且空间复杂度更低的方法？
容易发现，对于散块的查询是没有必要的，因为我们可以到时候 O(\sqrt n) 直接加入统计，所以问题被限制在左端点都是块的端点。
记录每个数在前 i 块的出现次数，到时候直接差分就好，这样的时间复杂度是 O((n+m)\sqrt n) 空间复杂度是 O(n\sqrt n)，实现较为简单，代码。
然后对于空间复杂度的问题……还记得之前的结论吗，出现次数大于 O(n^{1/4}) 的数，不超过 O(n^{5/4}) 的存储空间花费，出现次数小于 O(n^{1/4}) 的数，动态开点分块可以使得空间 O(n^{5/4})，然后就可以压空间，压到 O(n^{5/4})。
但是这种东西真的有人会打吗？它只是说明空间复杂度还是有优化的空间，那么可不可以进一步优化呢？
下面是个神奇的做法，它更好地利用了区间众数这个特殊问题的性质。
对于查询，我们只需要考虑散块的的贡献，然后就可以利用到一个性质：从整块的结束位置单调扫描，更新的区间众数的出现次数每次最多加一。
我们可以用 \text{vector} 按顺序维护每个数的出现次数和每个位置对应在 \text{vector} 的位置，这样就可以 O(1) 判断和拓展了。
看起来空间是 O(n) 时间是 O((n+m)\sqrt n) 的但由于空间线性，我们可以调节块长，O(\dfrac{n^2}B+Bm) 然后我们得到了时间复杂度 O(n\sqrt m)，空间复杂度 O(n+m) 的做法，代码。
你会发现这和我们一开始提到的“在线莫队”很像……所以思想是值得沿用的：我们可以暴力存储左右端点固定的信息，然后用端点拓展的方法（与莫队类似）。

再谈区间逆序对

强制在线，脚手架，这回咱们自己仔细思考怎么办。
它可以优化的原因你已经有所了解，正是因为它的可差分性，我们尝试用预处理块间信息，然后向散块拓展的方式。
设 f(i,j) 为第 i 块的元素a_x 与 a_j 满足 x<j 且 a_x>a_j 的数对个数，利用插入与查询的不平衡，它显然可以 O(n\sqrt n) 预处理，利用它的差分和前缀和可以快速求出整块对整块，散块对整块的贡献。
散块对散块的贡献是作者认为的难点，如果左右端点在同一块中：我们只需要预处理出每个点对于块中前后缀的贡献，然后跨过两个散块的贡献可以查询的时候直接归并，是容易的。
但是左，右端点在同一块中的情况呢？作者想了很久，然后发现可以用一个很简单的方法，前缀的贡献相减，然后用一个归并减去跨越的贡献，看来作者不擅长给自己的思维做减法啊！代码。
如果调块长可以做到时空复杂度 O(n\sqrt m)。

例题 15

例题 11，强制在线。
分块其实很好想，重点是复杂度怎么压。
目前我们需要预处理的是：每两块之间的答案和每个元素在每块内的前/后缀前驱/后继，两个散块我想的还是归并，然后预处理复杂度 O(n\sqrt n\log n) 单次查询的复杂度 O(\sqrt n)，稍微调节下块长还能优化。
但是复杂度怎么压呢？作者一开始是暴力预处理的，但是我们可以利用 \max 的一些性质，我们可以先处理出第 i 块和第 j 块分别选出一个数 a_x,a_y 的 |a_x-a_y| 的最小值，这个可以预先 O(n\log n) 排序处理是显然的，然后处理出这个就可以跑了，花式调块长，时空复杂度 O(n\sqrt m)。
然后另外一个的话，用归并也可以搞定，方法是枚举块中心的时候，对于整个数列的有序对单独考虑（这个可以一开始 O(n\log n) 排序）。
这两道题目很好的启示就是即使您轻松地想到了您 AC 这道题需要预处理什么信息，但是把预处理的信息稍作拆解往往能得到更好的复杂度，代码。

根号分治

所谓的“分而治之”，对不同特性的元素分别对待，或许可以得到较好的效果。
举个例子：给一个无向图，单点加，查询与某个点相邻的点的权值和。
对点的度数进行分治，度数大于 \sqrt m 的点不超过 \sqrt m 个，小度点在查询的时候暴力，大度点在更新的时候暴力，复杂度是对的。
这个东西在无向图三元环计数的时候会用到，就是很暴力地去找三元环，但是它能保证复杂度在 O(m\sqrt m)，很神奇。

例题 16

查询是 x 的数与是 y 的数的最小位置差。
对出现次数进行分治，可以 O(n\sqrt n) 时空记录每个数与大次数的最小位置差，接下来是小次数和小次数，归并计算即可。

例题 17

例题 17。
把询问离线以得到线性空间，然后就是出现次数分治了。

未完待续……