莫队算法

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队算法有了多种扩展版本。

概念

莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队

以下默认序列长度为 $n$，查询次数为 $m$。

有些奇怪的问题，线段树很难维护，比如，区间内的不同数字的个数。

经观察，如果已知一个区间 $[l,r]$ 的情况，可以 $O(1)$ 时间确定 $[l,r+1]$、$[l,r-1]$、$[l-1,r]$ 和 $[l+1,r]$ 的情况。

莫队算法的本质：对于离线处理的查询问题，通过合理安排这些区间计算的次序从而得到一个较优的复杂度。

已知区间 $[l,r]$，需要计算的区间是 $[l`,r`]$，由于 $l$ 和 $r$ 分别只能单步转移，所以需要的时间复杂度为 $O(|l`-l|+|r`-r|)$。

把一个查询对应成平面上的一个点，每次转移的花费就是两点之间的曼哈顿距离，所有查询的最小花费就是使这些点联通的最小曼哈顿距离，这就成了一个最小生成树问题。

可以用分块算法平衡一下时间复杂度和代码复杂度，达到时间复杂度 $O(n \sqrt m+m \log m)$。

序列分块后，以查询左端点所在块为第一关键字，以右端点大小为第二关键字，从小到大排序。

设块大小为 $B$，那么左端点移动总次数为 $O(mB)$，右端点移动总次数为 $O(\dfrac{n^2}{B})$，总时间复杂度为 $O(mB+\dfrac{n^2}{B})$，当 $B=\sqrt{\dfrac{n^2}{m}}=\dfrac{n}{\sqrt m}$，取到最优值 $O(n \sqrt m)$。

回滚莫队

在一些情况下，莫队维护的区间便于增加元素而不便删除元素（或反之），则要使用回滚莫队以避免不方便的操作。

（以下默认区间已按照左端点 $a$ 所在块 $\mathrm{belong}_a$ 为第一关键字，右端点 $b$ 为第二关键字排序完成。）

对于 $\mathrm{belong}_a=\mathrm{belong}_b$ 的操作，直接暴力求出答案。

如果不便于删除，则如果当前询问区间的左端点 $a$ 在新的一块，则重置莫队维护的区间为 $[r_{\mathrm{belong}_a}+1,r_{\mathrm{belong}_a}]$（空区间）；然后先将当前询问区间的右端点多出的部分补齐，新建临时变量，再将当前询问区间的左端点多出的部分补齐后的结果存入临时变量。存储好答案后将刚刚对左端点补齐的部分删除（即“回滚”），答案不受影响。这样就避免了删除的操作。

如果不便于增加，则如果当前询问区间的左端点 $a$ 在新的一块，则重置莫队维护的区间为 $[l_{\mathrm{belong}_a},n]$；然后先将当前询问区间的右端点多出的部分删除，新建临时变量，再将当前询问区间的左端点多出的部分删除后的结果存入临时变量。存储好答案后将刚刚对左端点删除的部分恢复（即“回滚”），答案不受影响。这样就避免了增加的操作。

带修改莫队

如何解决数据的修改？

添加一个时间轴，坐上时光穿梭机。

指令处理，将询问和修改分开：

1. 修改指令记录修改位置、修改前值、修改后值。
2. 询问指令记录左右端点、$x$（在此之前做过 $x$ 次修改）、$\mathrm{id}$（第 $\mathrm{id}$ 个查询）。
3. 查询指令排序：第一关键字 $l$ 所在块，第二关键字 $r$ 所在块，第三关键字 $x$。

查询时，如果当前修改数比询问的修改数少，补做修改；否则回退。

修改时，如果修改在当前区间，同时需要更新答案。

复杂度分析（假设块大小为 $B$，修改次数为 $c$，查询次数为 $q$）：

• 时间指针 $\mathrm{now}$，每个查询的分块组合最坏情况会移动 $c$，总移动次数为 $O(\dfrac{cn^2}{B^2})$。
• 左端点 $l$，分块相同时最多移动 $B$，换分块时最多移动 $2B$，总移动次数为 $O(qB)$。
• 右端点 $r$，左端点不换分块时，右端点不换分块移动次数为 $B$，换分块时移动次数为 $2B$，总移动次数为 $O(qB)$；左端点换分块时，最多移动次数为 $n$，总次数为 $O(\dfrac{n^2}{B})$。

总移动次数为 $O(\dfrac{cn^2}{B^2}+qB+\dfrac{n^2}{B})=O(\dfrac{mn^2}{B^2}+mB+\dfrac{n^2}{B})$，取 $c=q=O(m)$。

$O(\dfrac{mn^2}{B^2}+mB+\dfrac{n^2}{B})$ 在 $B=n^{\frac{2}{3}}$ 时取到最小值 $O(n^{\frac{2}{3}}m)$。

莫队配合 bitset

树上莫队

参考资料

• 『回滚莫队及其简单运用』 - Parsnip - 博客园