莫队算法是一种根号复杂度离线算法，也与分块、定期重构并称优雅的暴力。
普通莫队的时间复杂度是 $O(m\sqrt n)$，此外还有许多变种。
普通莫队
当我们遇见一类没有修改的问题时如何处理？
假设我们已经求出了在 $[l,r]$ 上的答案，我们想求出 $[l^\prime,r^\prime]$ 的答案，怎么办？
如果我们能够快速地将答案从 $[l,r]$ 转移到 $[l-1,r]$，$[l+1,r]$，$[l,r+1]$，$[l,r-1]$ 这四个区间上，我们就可以一步步地将 $[l,r]$ 转移到 $[l^\prime,r^\prime]$ 上。可惜这样的时间复杂度不够优秀，达到了 $O(n)$ 一次转移。怎么优化呢？
普通莫队算法将这些询问离线下来，以一种方式排序后重新计算答案，方式是：
- 对原序列分块，块长为 $\sqrt n$。记 $\operatorname{block}(p)$ 为 $p$ 所属的块。
- 对于两个询问 $[l_1,r_1]$，$[l_2,r_2]$，如果 $\operatorname{block}(l_1)\neq\operatorname{block}(l_2)$，那么块编号小的在前面。
- 否则 $r$ 小的在前面。
以这样的顺序转移，时间复杂度只需要 $O(m\sqrt n)$。
复杂度证明：
设块长为 $B$。
首先右端点在左端点块编号保持不动时一共只会移动 $O(n)$ 次，因为右端点编号不降。
其次考虑左端点的移动。在块编号不变时每次移动会移动 $O(B)$ 次。在块发生变化时也会移动 $O(B)$ 次，而一共会发生 $O(n/B)$ 次移动，并且一次移动右端点要回来，也会开销 $O(n)$ 的时间。
所以总复杂度开销是 $O(n/B\cdot (n+B)+nB)=O\left(\dfrac{n^2}{B}+nB\right)$，显然在 $B=\sqrt n$ 是最小，为 $O(n\sqrt n)$。以上默认 $m,n$ 同阶。
这样莫队算法就用 $O(n\sqrt n)$ 的时间解决了问题。
普通莫队奇偶排序优化
就是说，奇数块的询问右端点从小到大排序，偶数块的询问右端点从大到小排序。
感性理解一下这就是不要右端点再回来了，路上直接完成操作。据说能快 30%？
例题 小 Z 的袜子：
有一个长度为 $n$ 的数列 $a_1,a_2,\dots,a_n$，有 $m$ 次询问，每次询问给定 $l_i,r_i$，你需要在区间 $[l_i,r_i]$ 中选取两个不同的整数 $i,j$，求 $a_i=a_j$ 的概率。
$n,m\le5\times10^4$。
一打眼看上去，$n,m$ 较小，可以采用时间复杂度带根号的算法。并且可以离线，使用莫队求解。
显然是好做的。我们将 $a$ 离散化后开值域数组，当加入删除一个数的时候统计并计算答案，时间 $O(1)$。
所以时间复杂度 $O(n\sqrt n)$。
带修莫队
普通的莫队是不能支持修改的。
我们可以让操作从 $(l,r)$ 强行变成 $(l,r,\mathrm{time})$，其中 $\mathrm{time}$ 是时间维，代表此次操作前面有 $\mathrm{time}$ 次修改。
只需要我们能够从 $(l,r,\mathrm{time})$ 快速转移到
- $(l-1,r,\mathrm{time})$，$(l+1,r,\mathrm{time})$；
- $(l,r-1,\mathrm{time})$，$(l,r+1,\mathrm{time})$；
- $(l,r,\mathrm{time}-1)$，$(l,r,\mathrm{time}+1)$。
这六种状态，我们就可以使用扩展的莫队求解。排序方式是左端点块编号第一关键字，右端点块编号第二关键字，$\mathrm{time}$ 第三关键字，块长 $O(n^{\frac23})$，总时间复杂度为 $O(n^{\frac53})$，如果 $n,m,t$ 同阶。
复杂度证明：
设 $n,m,t$ 表示大小、询问次数、修改次数。$B$ 为块长。
首先我们不能不将右端点分块，因为有序的右端点会带来乱序的询问，与不对右端点排序的时间开销都是 $O(n)$。
我们不妨设 $q_{i,j}$ 表示左端点在块 $i$、右端点在块 $j$ 的询问次数。
对于 $q_{i,j}$ 内的询问，时间维变化次数是 $O(t)$，左右端点移动次数是 $O(B)$。
那么总时间复杂度是
考虑求此式最小值，利用求导法，设 $\mathsf{time}(B)=mB+\left(\dfrac{n}{B}\right)^2t$，那么 $\mathsf{time}^\prime(B)=m-\dfrac{2n^2t}{B^3}$。
令 $\mathsf{time}^\prime(B)=0$，即 $B=\sqrt[3]{\dfrac{2n^2t}{m}}$。当 $n,m,t$ 同阶时 $B=O(n^{\frac23})$ 最优。总时间复杂度为 $O(n^{\frac53})$。
回滚莫队
回到没有修改的情况。
然后你发现出题人没有这么良心，不妨假装你发现 $(l,r)$ 无法扩展到 $(l+1,r)$ 和 $(l,r-1)$，即你无法支持删除操作。
这时候你还想保住你的莫队！于是你要找一个能只增不删的方法，这就是回滚莫队。
我们在更换块的时候令 $R$ 为当前新块的右端点，并设置 $r=R,l=r+1$。这是一个空区间。
我们在处理问题的时候，如果 $\operatorname{block}(l)=\operatorname{block}(r)$ 就直接暴力扫描处理，否则扩展左端点和右端点。右端点单调递增不用管，左端点每次更新完后都滚回到 $R+1$ 重新扩展。由于 $l$ 一次滚回只会有 $O(\sqrt n)$ 的时间开销，因此不会造成复杂度的退化。
回滚莫队通用模板，其中 $\mathrm{add},\mathrm{del}$ 函数是增加或删除的函数。（删除就是直接撤销增加的影响但是不管答案，答案已经在滚之前就记录下来了，直接恢复。）
1 | ll r=bl(q[1].l)*sqr,l=r+1; |