浅谈 Method of Four Russians

critnos · 2021-09-15 13:17:20 · 算法·理论

（如果文章有什么错误请指出）

前言

今年（2021）的 CSP-S 初赛的最后一题就是这个东西。救我一程。

这个东西是非常有趣的。可惜的是，他在序列或树上半群并不 practical（我认为）。因为我们有简单的严格 \Theta(n) 预处理，期望 O(1) 询问的区间（链上）半群信息维护方法。

例 1

以经典题目引入：

给出一个序列，相邻两项之差为 \pm1，每次求区间最大值。

序列分块，块长 b=\dfrac {\log n} 2。

将每块的最大值提取出来，得到一个长为 \Theta(\dfrac n {\log n}) 的序列。

那么对这个序列建立 ST 表，就可以完成求 l,r 之间整块的最大值的任务。这个 ST 表建表的复杂度是 \Theta(\dfrac n {\log n} \log(\dfrac n {\log n}))=\Theta(n)。

那么现在问题转为了求散块内的最大值。即一个长为 b 的序列的区间最大值。

既然序列长度为 b=\dfrac {\log n} 2，那么肯定要利用好这个特性。

注意到相邻两项之差为 \pm1。就是说把这个长度为 b 的序列建立差分序列，这个差分序列有 2^{b-1} 种。而每个差分序列所对应的序列的每个子段的答案都可以预处理出来。复杂度为 \Theta(2^{b}b^2)=\Theta(\sqrt n \log ^2n)=O(n)。

事实上这里可以 b=k\log n,k\in(0,1)。

我们称两块本质不同，当且仅当两块的差分序列不同。

那么我们把每个块映射到预处理出来的对应的差分序列上，直接查询即可。

举个例子：

两个块 1 2 3|4 5 6。

那么差分序列是 0 1 1|0 1 1。

这个 0 1 1 所对应的序列是 0 1 2。

那么预处理出 0 1 2 这个序列的每个子段的最大值。（其实我们要预处理的是所有不同的差分数组共 2^{b-1} 个，这里为了方便，只展示一个）。

比如查询 [2,3] 的最大值，我们就找到预处理出的答案 2（序列 0 1 2 的区间 [2,3] 的最大值）再加上 1。因为这个差分序列所对应的序列要整体上移 1 才能得到原序列。

那么我们就 \Theta(n)-\Theta(1) 地解决了该问题。

解法和 CSP-S 2021 初赛的解法略有不同。这个更加广义一些。

差分序列只是在这个例子种因为题目特性而成为判断本质不同的一种方法，后文的阅读中，不要将思想局限于差分序列。

例 2

更进一步的：

给出一个序列，每次求区间最大值。

考虑用 O(n) 的时间转为例 1。

对序列求出笛卡尔树。

那么区间最大值就转为了 LCA。（笛卡尔树基本性质）

对笛卡尔树求出欧拉序。那么 LCA 问题转为了 RMQ（区间最值）问题。

考虑到这个序列的相邻两项之差为 \pm1，那么就转为了例 1。

上面每一步的时间复杂度均为 \Theta(n)。

例 3

给出一个序列，每次求区间严格众数（出现次数大于区间长度的一半）。若不存在则任意输出。

之所以可以“任意输出”，是因为 check 求出来的答案是否确实为区间严格众数与主题无关。我可以给出一个离线的简单做法 ^1，文献 2 中有一个在线做法。同时需要知道这个是一个半群信息，也可以在文献 1 看。

还需要知道序列上区间半群是可以 \Theta(n \log n)-\Theta(1) 做的 ^3。

考虑一下本质不同的情况是什么。很显然就是这个序列的每个数都在 [1,b] 内。而我们对原序列的每个块离散化（这里离散化不要求保留大小关系，可以用 hash），再使用 hash 识别这个块属于哪个本质不同的情况。

唯一的问题就是本质不同的情况个数。有 \Theta(b^b) 个。b=\Theta(\log n) 的方法不 work 了。

所以就要在保证整块处理的时间复杂度仍为 O(n) 的情况下，把 b 降下来。

我们把这个结构迭代一层，即对块内继续分块。那么这时候块长下降到了 b'=\Theta(\log \log n)。注意在使用两层分块的时候，第一层分块的块大小的常数无关紧要，我们取第一层的块长 b=\Theta(\log n) 即可。

此时预处理时间复杂度为 \Theta(b'^2 b'^{b'})。考虑证明 \Theta(b'^2 b'^{b'})=O(n)。

两边取对数得到 \Theta(b'\log b')=O(\log n)。代入得到 \Theta(\log \log n\log \log \log n)=O(\log n)。得证。

故而我们 \Theta(n)-\Theta(1) 地解决了这个问题。

这个思想是很有用的。在令 b'=\Theta(\log \log n) 后（甚至可以继续迭代下去），瓶颈基本上就在于识别原序列每块属于哪个本质不同的情况了。

例 4

介绍一个上树的方法：

给出一棵树，边带权（\pm1），每次查询两点之间路径上的最大子链和。

要会 top cluster ^4 对树分块。

（虽然说 top cluster 不保证每个块大小为严格的 b，不过我们断言，这个没有影响）

最大子链和是一个经典的半群信息。也就是说我们要在收缩树上做半群信息维护。

考虑对收缩树建立点分树，O(n\log n)。会发现两点之间的信息可以用这两点在点分树上的 LCA 合并。那么做一个 O(n\log n)-\Theta(1) 的 LCA 即可。这里的 n 指收缩树规模。

那么当簇大小 b=\Omega(\log n) 时，收缩树规模为 O(\dfrac n {\log n})。这样就是 O(n)-\Theta(1) 的。这个方法的本质就是把序列上的二区间合并放到了树上。

那么现在的问题仍是两点在同一簇内。即一个大小为 b 的树的询问。

如何表示本质不同的簇（树）？首先是树的结构。一个很好的方法是，把每个点的父亲记录下来。粗略估计下来，共有 (b-1)! 种。

然后是边权。这个就是 2^{b-1} 种。

还是做两层 top cluster 分块，第一层 b=\Theta(\log n)，第二层 b'=\Theta(\log \log n)。

那么要证明 \Theta((b'-1)!2^{b'-1}b'^2)=O(n)。

显然两边取对数得到 \Theta(b' \log b')=O(\log n)。代入得到 \Theta(\log \log n \log \log \log n)=O(\log n)。得证。

最后一步，识别每个簇属于哪个本质不同的情况。这个也可以用 hash 解决。

于是我们 \Theta(n)-\Theta(1) 地解决了这个问题。

例 5

一些奇特的应用（来自和 w33z 的讨论）：

给出一个序列，数的种类数为 c（c 为常数），每次修改单点修改（保证数的种类数仍为 c），每次询问查询区间最大子段和。要求 O(1) 修改。

设块长为 b，要保证 c^b\le n。

两边取对数得到 b\log c\le \log n，得到 b\le \dfrac {\log n} {\log c}。

每个块用一个 word 表示出来（word-RAM model 告诉我们可以这么做）。

然后单点修改可以 O(1) 改变这个块所对应的 word。利用 word 做映射，我们就可以在 O(1) 的时间内得到关于这个块的已经被预处理出的信息的位置。

那么查询的时候，直接暴力扫，就可以做到 \Theta(\dfrac n {\log n}) 的查询时间复杂度。

这里介绍的是用四毛子加速特殊的维护区间半群信息 O(1) 修改的方法。这样做的瓶颈在于单点修改后改变这个块对应信息的映射位置。事实上，区间严格众数也可以用类似的方法做到 \Theta(\dfrac n {\log \log n}) 的查询时间复杂度。

对于这题，若 c=2，每个数 \in\{1,-1\}，可以继续优化。我们发现，对于整块的信息，我们可以粗略估计上界得到有 O(b^4) 个本质不同的块。

那么对于由整块组成的长度为 \Theta(\dfrac n {\log n}) 的序列，我们继续分块。设块长为 b'，那么要保证 (\log^4 n)^{b'}\le n。

两边取对数得到 4b'\log \log n\le \log n。得到 b'\le \dfrac {\log n} {4\log \log n}。

那么我们得到了一个 \Theta(\dfrac {n \log \log n} {\log ^2 n}) 的做法。

这个方法是进一步的识别本质不同的块，不过适用面会更窄一些。

思考题

给出一棵树，每次查询一个点的若干级祖先 ^5。

给出一棵树，每次操作将一个节点合并到父亲，每次询问查询一个点已合并的祖先 ^6。

给出一棵树，边带权。每次查询两点之间路径上边权的最大值 ^7（提示：瓶颈在于整数排序！如何线性地对 O(\log n/\log \log n) 个数排序呢！）。

给出一个序列，每次修改单点修改，每次询问查询区间严格众数（若不存在则任意输出）。要求 O(1) 修改，o(\dfrac n {\log \log n}) 查询。

参考文献

1. dqstz 题解 P7252 [JSOI2011] 棒棒糖
2. hqztrue 一个RMQ问题的快速算法，以及区间众数
3. Judge_Cheung 一种神奇的数据结构——猫树
4. 周欣 《浅谈一类树分块的构建算法及其应用》（2021 国家集训队论文）
5. 约瑟夫用脑玩 易懂科技：将LCA、RMQ、LA优化至理论最优复杂度
6. ljt12138 RMQ标准算法和线性树上并查集
7. 感谢 myh 学长，ccz，lxl 的指导！