离线算法学习笔记

莫队

适用范围：符合一定条件的多元询问。

假设需要回答一系列询问，每个询问有两个参数 $Q_i=(x,y)$（$1\leq x,y\leq n$）。

以下认为 $n,q$ （询问次数）为同一量级。

莫队的核心假设是：通过已知的 $(x,y)$ 询问的答案，很快速地得到 $(x±1,y)$ 或 $(x,y±1)$ 的答案。设转移复杂度为 $O(k)$ 。莫队的算法流程为：

将所有询问离线下来，将 $n$ 分为 $\sqrt n$ 块。把所有第一维坐标在同一块内的所有询问分为一组，这样询问就分成了 $\sqrt n$ 组。对于每一组，将该组的询问按照第二个维度的坐标进行升序排序，这样，对于同一组内的每次游走，一维坐标改变不超过 $\sqrt n$ 次，二维坐标始终是单调不降的，对于这整个组的复杂度为 $O(n)$ 的。由于总共有 $\sqrt n$ 个组，组与组之间转移为 $O(n)$ ，总转移次数为 $O(n\sqrt n)$，复杂度为 $O(nk\sqrt n)$ 。

对于 $m$ 的其他取值，块长为 $\dfrac{n}{\sqrt m}$ 是最优的，复杂度为 $O(n \sqrt m)$ 。

以上主要是莫队在二维时的情形，接下来讨论 $k$ 维的情形。假设询问可以描述成一个 $k$ 元组 $(a_1,\dots ,a_k)$ ，如果我们通过 $(a_1,\dots ,a_k)$ 的答案，可以较快速的得到 $(a_1,\dots ,a_i±1, \dots a_k)$ 的答案，就可以看作是在一个 $k$ 维空间内进行单位长度的游走。将序列分成 $n^{\frac{1}{k}}$ 块，每块长度为 $n^{\frac{k-1}{k}}$。仿照二维的情形，将前 $(k-1)$ 元素都在同一块内的放在同一组，然后对第 $k$ 个进行排序和游走，这样分为了 $n^{\frac{k-1}{k}}$ 组。可以类比二维时的时间复杂度分析，总的时间复杂度是 $O(n^{2-\frac{1}{k}})$ 。

例题：P1903（可以将时间视作一个空间参数，三维莫队），P1494

树上（括号序列）莫队

例：树上数颜色，每次求一个树链上的颜色个数。

括号序：DFS一棵树，首次到达这个节点的时候将其加入队列（记这个为开始点），DFS完这个节点（准备向上到父节点）时再次将这个点加入队列（记为结束点）。每个点一定会在括号序内出现 $2$ 次。

考虑树链的情况，记树链为 $u$ 到 $v$，可以分为两组。

1. $u$ 是 $v$ 的祖先。考虑从 $u$ 的开始点到 $v$ 的开始点的区间，此时树中的点可以分为 $3$ 类。

   1. $u$ 到 $v$ 链上的点。这些点只会出现一次，且都为这些点的开始点。
   2. 不在链上，但是 $u$ 是其祖先的节点。这些点有可能会加入两次（搜到了，然后回溯到了链上某点），有可能没被DFS到，未出现。
   3. 其他点，出现 $0$ 次。

2. $u$ 和 $v$ 的LCA为 $c$ 。此时考虑从 $u$ 的结束点到 $v$ 的开始点的区间（设 $u$ 的结束点在 $v$ 的开始点之前），则整个树可以分成 $4$ 类。

   1. 在 $u$ 到 $c$ 的路径上（不包含 $c$）。这些点一定在这个区间内出现了 $1$ 次（结束点）。
   2. 在 $v$ 到 $c$ 的路径上（不包含 $c$）。这些点一定在这个区间内出现了 $1$ 次（开始点）。
   3. 点 $c$ ，一定不在区间内，可以在区间移动完后额外添加，询问完后删除。
   4. 剩下的点，不会出现。

发现所有在路径上（除 $c$）都只出现了一次，因此我们可以开一个辅助数组标记这个点是否在路径上，每次经过的时候^=1。

我们将询问 $[l,r]$ 转化为在括号序上的 $[st_l,st_r]$ 或者 $[st_l,ed_r]$，其中 $st$ 代表开始点，$ed$ 代表结束点。这样就转化为了序列上的问题，套用普通莫队即可解决。

例题：SP10707，P4074

回滚莫队

有时候，从询问 $(l,r)$ 扩展到 $(l-1,r+1)$ 和扩展到 $(l+1,r-1)$ （即删除和添加操作）的复杂度是不同的，比如区间众数，或者一段区间内相同数的最远距离。

这里暂时只考虑二维的情况，记询问为 $(l,r)$ 。

此时我们更改转移过程。块之间转移只有 $\sqrt n$ 次，因此每次可以直接清空莫队，重新开始。对于块内，我们依旧按 $r$ 排序，但我们每次都让莫队的 $l$ 端点位于该块的右端点。对于每一组询问，先扩展 $r$ ，然后扩展 $l$，（因为询问的 $l$ 一定不大于这一块的右端点，因此一定是扩展的）。这样 $l$ 的移动次数依旧是 $\sqrt n$ 的。在获得完这次询问的答案后，我们并不删除 $l$ 端点，而是回退到刚刚扩展完 $r$ ，且 $l$ 在块右端点的状态，这样我们通过撤销扩展代替了删除，可以规避删除的高复杂度。

对于这样的莫队，取一个形象的名字叫“回滚莫队”。

例题：P5906

莫队二次离线

CDQ分治

CDQ分治是用来解决一类可以表述为这样的问题：每个修改 $x$ 可以用 $k$ 维坐标 $(a_1,a_2,...,a_k)$ 表示，每个询问 $q$ 亦可用 $k$ 维坐标 $(b_1,b_2,...,b_k)$ 表示，代表答案由满足 $\forall 1\leq i \leq k,a_i\leq b_i$（记为偏序关系 $(a_1,a_2,...,a_k) \preceq (b_1,b_2,...,b_k)$）的所有修改决定。具体地，满足条件的修改为 $x_1,x_2,...,x_m$，则答案为 $x_1 \oplus x_2 \oplus ... \oplus x_m$，$\oplus$ 为满足结合律和交换律的运算。交换律代表这些贡献计算的顺序无关紧要，结合律意味着可以将修改分为几个部分（分治）分别计算后合并。

一个符合要求的例子就是每个询问想要知道满足偏序关系的修改的个数，那么答案就是 $1+1+...+1$ 。这里 $x_i$ 取 $1$（每个修改计算一次），$\oplus$ 取$+$（满足结合律，交换律）。

因为 $k$ 个维度的要求具有独立性，可以考虑逐个击破，即先按第一维坐标排序，这样对于所有询问第一维的限制就被反映在前后顺序中，询问所需的修改就是“在它之前且后 $k-1$ 个维度满足偏序关系”的修改。

cdq分治的核心就是将第一维进一步分治：对当前序列按顺序均分为两段，修改对于询问的贡献可以分为“左修改对左询问”，“右修改对右询问”，“左修改对右询问”三种。前两种可以继续分治，对于第三种，发现这个询问在第一维一定满足偏序关系，将这类视作一个新的子问题，那么需要考虑的偏序关系就只剩下后 $k-1$ 维，亦可递归计算。

底层情况就是 $k=1$ 时偏序关系就是顺序，暴力计算；或者 $k$ 比较小的时候可以用在线数据结构代替进一步的分治。

一个优化：我们在求解第 $k$ 维的时候，可以参考归并排序，使左右递归的问题返回后已经按照第 $k+1$ 维排序，这层只需 $O(n)$ 归并即可，能省一些可能因为排序出现的复杂度提升。

以暴力扫描作为底层，分解每一个维度时，修改、询问会被拆分为 $O(\log n)$ 个，因此总复杂度为 $O(n\log^{k-1} n)$。

例：P3810