简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 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}$，把每个点分入一个块内，然后将所有询问按照左端点所在块为第一关键字排序，右端点的序号为第二关键字排序。

下面我们来解释下为什么要这么做：

1. 所在块相同时，右端点递增是 $O(N)$ 的，块共有个 $O(\sqrt{N})$，复杂度为 $O(N^{1.5})$
2. 分块转移时，右端点最多变化 $N$，块共有 $O(\sqrt{N})$ 个，复杂度为 $O(N^{1.5})$
3. 块相同时，左端点最多变化 $\sqrt{N}$，块转移时，左端点最多变化 $2\sqrt{N}$，共有 $N$ 个询问，复杂度为 $O(N^{1.5})$

所以总时间复杂度为 $O(N^{1.5})$。

Code

莫队的劣处

不难发现，莫队只支持离线区间询问，对于在线问题，我们并不能采用莫队来解决。

并且使用莫队需要一些卡常技巧，才能战胜出题人。

带修莫队

一般的莫队是不支持修改的，但是如果我们稍微修改一下，就可以让莫队资瓷修改啦~

就像 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$ 次询问或修改。

题目需要你进行的操作有：

1. Q l r 表示询问 $[l,r]$ 中出现过的数值种类数。
2. R p col 表示把第 $p$ 个数替换成颜色 $col$。

Solution

带修莫队模板

Code

树上莫队

直接类似于树分块，直接在 $Dfs$ 时，如果子树大小超过块大小就直接合成一个块即可。

其他操作类似于普通莫队。

显然，如果直接这样操作肯定是不行的。

因为两个端点还是需要计数的。

容易想到，只有 $LCA$ 才可能重复，所以每次不标记 $LCA$，询问答案时再标记，最后撤销即可。

例题：LuoguP4074 [WC2013] 糖果公园

Code

回滚莫队

例题：AT1219 歴史の研究

Solution

回滚莫队类似于普通莫队进行排序。

查询直接枚举每一个块，而该块所有右端点都是单调递增的，而左端点都在同一个块内移动，从而计算每个询问的值。

每次到下个块的左端点直接全部清空即可。

Code