浅谈莫队
简介
莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。
莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
-- OI wiki
普通莫队
引例：区间不同数
Description
有一个长度为 $n$ 的序列，有 $m$ 次询问，每次询问某个区间内出现过的数值种类数。
$1\leq n \leq 5\times 10^4,1\leq m \leq 2\times 10^5,0\leq a_i \leq 10^6$
Solution
首先考虑暴力，如果对于每一个询问，直接暴力枚举区间每个数，开个桶统计每个数字是否出现过，显然这种做法会超时，复杂度为 $O(NM)$。
这时候就要用到莫队算法了。
那么莫队是什么呢？
其实就是优雅的暴力。
我们现在可以思考一个问题，如果你已经得知区间 $[l,r]$ 的答案，那么如何求区间 $[l,r+1]$ 的答案呢？
显然区间 $[l,r+1]$ 只比 $[l,r]$ 多了元素 $a[r]$，那么我们只需要判断 $a[r]$ 对答案是否有贡献即可。
那么什么时候 $a[r]$ 对答案有贡献呢？
显然只有当区间 $[l,r]$ 中 $a[r]$ 的出现次数为 $0$。
那么事情就很好办了，我们只需要开一个 $cnt$ 数组统计每个数字目前出现的次数，每次对答案造成贡献的条件是 $cnt[a[r]]==0$。
同理，我们如果知道了区间 $[l,r]$ 的答案，我们就可以知道 $[l-1,r],[l+1,r],[l,r-1]$ 的答案。
而且这个复杂度是 $O(1)$ 的，那么处理下一个询问的复杂度就是 $O(r_i-r_{i-1}+l_i-l_{i-1})$ 的。
这样的复杂度在随机数据中表现很好，但是毒瘤的出题人也不难卡你。
那么此时就需要莫队优化的精髓来减小复杂度了。
我们考虑进行分块，不妨设块大小为 $\sqrt{N}$，把每个点分入一个块内，然后将所有询问按照左端点所在块为第一关键字排序，右端点的序号为第二关键字排序。
下面我们来解释下为什么要这么做：
- 所在块相同时，右端点递增是 $O(N)$ 的，块共有个 $O(\sqrt{N})$，复杂度为 $O(N^{1.5})$
- 分块转移时，右端点最多变化 $N$，块共有 $O(\sqrt{N})$ 个，复杂度为 $O(N^{1.5})$
- 块相同时，左端点最多变化 $\sqrt{N}$，块转移时，左端点最多变化 $2\sqrt{N}$，共有 $N$ 个询问，复杂度为 $O(N^{1.5})$
所以总时间复杂度为 $O(N^{1.5})$。
Code
1 |
|
莫队的劣处
不难发现，莫队只支持离线区间询问，对于在线问题，我们并不能采用莫队来解决。
并且使用莫队需要一些卡常技巧，才能战胜出题人。
带修莫队
一般的莫队是不支持修改的，但是如果我们稍微修改一下，就可以让莫队资瓷修改啦~
就像 DP 一样，可以强行加上一维时间维, 表示这次操作的时间。
时间维表示经历的修改次数。
即把询问 $[l,r]$ 变成 $[l,r,time]$。
那么我们的坐标也可以在时间维上移动，即 $[l,r,time]$ 多了一维可以移动的方向。
这样的转移也是 $O(1)$ 的，但是我们排序又多了一个关键字，再搞搞就行了。
可以用和普通莫队类似的方法排序转移，做到 $O(N^{\frac{5}{3}})$。
这一次我们排序的方式是以 $N^{\frac{2}{3}}$ 为一块，分成了 $N^{\frac{1}{3}}$ 块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。
还是来证明一下时间复杂度：
- 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是 $O(N)$；
- 若左右端点所在块改变，时间一次最多会移动 $N$ 个格子，时间复杂度 $O(N)$；
- 左端点所在块一共有 $N^{\frac{1}{3}}$ 中，右端点也是 $N^{\frac{1}{3}}$ 种，一共 $N^{\frac{1}{3}}$ 种，每种乘上移动的复杂度 $O(N)$，总复杂度 $O(N^{\frac{5}{3}})$。
例题：LuoguP1903 [国家集训队]数颜色 / 维护队列
Description
有一个长度为 $n$ 的序列，要支持 $m$ 次询问或修改。
题目需要你进行的操作有：
Q l r表示询问 $[l,r]$ 中出现过的数值种类数。R p col表示把第 $p$ 个数替换成颜色 $col$。
Solution
带修莫队模板
Code
1 |
|
树上莫队
直接类似于树分块，直接在 $Dfs$ 时，如果子树大小超过块大小就直接合成一个块即可。
其他操作类似于普通莫队。
显然，如果直接这样操作肯定是不行的。
因为两个端点还是需要计数的。
容易想到，只有 $LCA$ 才可能重复，所以每次不标记 $LCA$，询问答案时再标记，最后撤销即可。
例题：LuoguP4074 [WC2013] 糖果公园
Code
1 |
|
回滚莫队
例题：AT1219 歴史の研究
Solution
回滚莫队类似于普通莫队进行排序。
查询直接枚举每一个块，而该块所有右端点都是单调递增的，而左端点都在同一个块内移动，从而计算每个询问的值。
每次到下个块的左端点直接全部清空即可。
Code
1 |
|