概述
莫队算法的用武之地是一类询问可以离线，且可以通过区间 $[l,r]$ 的答案在 $\mathcal O(1)$ 或 $\mathcal O(\log n)$ 得到区间 $[l\pm 1,r]$ 或 $[l,r\pm 1]$ 的答案的问题。它通过对询问离线、分块和排序，巧妙地将时间复杂度从 $\mathcal O(nm)$ 优化到 $\mathcal O((n+m)\sqrt n)$。
例题
我们以「BZOJ 2038」小 Z 的袜子 为例。
小 Z 有 $n$ 只袜子，每只袜子都有一个颜色 $c_i$。他有 $m$ 次询问，每次询问给出一个区间 $[l,r]$，求出在这个区间里随机抽 $2$ 只袜子，这 $2$ 只袜子有多大的概率颜色相同。
数据范围：$1 \le n, m \le 5 \times 10^4$。
算法分析
例题中区间的信息没有区间可加性，因此无法用数据结构进行维护，
首先我们分析一下是否可以使用莫队解决，对于区间 $[l,r]$，答案为 $\dfrac{\sum_{i=1}^n \binom{f(i)}{2}}{\binom{r-l+1}{2}}$（其中 $f(i)$ 表示当前区间内颜色 $i$ 出现的次数）。如果要求出区间 $[l+1,r]$ 的答案，只比原先少了一个 $c_l$，我们把分子分母分开考虑：
- 分子：在颜色 $c_l$ 中选择的方案数变少，减少了 $f(c_l)-1$ 种方案数。
- 分母：就是新的区间长度 $r-l$ 中选 $2$ 个数的方案数 $\binom{r-l}{2}$。
对于向其他几种新区间的转移过程也是可以的，读者可以自行尝试分析。接下来我们就来了解一下莫队算法的过程！
排序
把所有的询问离线，把询问左端点 $l_i$ 以 $\sqrt{n}$ 的大小进行分块，记第 $i$ 个询问左端点所在的块为 $b_i$，以 $b_i$ 为第一关键字，$r_i$ 为第二关键字进行排序。那么整体的 $b_i$ 是有序的，同一个块中的 $r_i$ 是有序的。
询问
其实这个转移并没有什么技巧，反而非常非常非常暴力！
如果我们已经知道了 $[L,R]$ 的信息，现在需要计算 $[l,r]$ 的答案，那我们直接把 $L$ 暴力移动到 $l$，把 $R$ 暴力移动到 $r$ 即可。
证明
了解完莫队的暴力转移过程，我们就要优美地证明这个过程并不暴力！
离线询问的整个过程中，只有 $L$ 和 $R$ 在不断移动并且两者独立，所以我们分别考虑。
左端点
- 相同块：左端点每次最多移动 $\mathcal O(\sqrt n)$ 的距离，有 $\mathcal O(m)$ 个询问。那么同一个块中左端点的移动距离为 $\mathcal O(m\sqrt n)$。
- 跨越块：左端点每次最多移动 $\mathcal O(\sqrt n)$ 的距离，有 $\mathcal O(\sqrt n)$ 次跨越块。那么跨越块导致左端点的移动距离为 $\mathcal O(n)$。
右端点
- 相同块：右端点每次最多移动 $\mathcal O(n)$ 的距离，有 $\mathcal O(\sqrt n)$ 个块。那么同一个块中右端点移动距离为 $\mathcal O(n\sqrt n)$。
- 跨越块：右端点每次最多移动 $\mathcal O(n)$ 的距离，有 $\mathcal O(\sqrt n)$ 次跨越块。那么跨越块导致右端点移动距离为 $\mathcal O(n\sqrt n)$。
综上所述，莫队算法的复杂度为 $\mathcal O((n+m)\sqrt n)$。
代码
莫队的代码非常套路，这份代码就当做是一个模板吧！
#include <cstdio>
#include <cmath>
#include <algorithm>
const int N = 5e4 + 5;
int n, m, a[N], b[N], cnt[N];
long long res, ansx[N], ansy[N];
struct Data {
int l, r, id;
bool operator < (const Data &b) const {
return b[l] == b[b.l] ? r < b.r : l < b.l;
}
} q[N];
long long query(int x) {
return 1LL * x * (x - 1) / 2;
}
void add(int x) {
res += cnt[x]++;
}
void del(int x) {
res -= --cnt[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
for (int i = 1; i <= m; i++) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].id = i;
}
int len = sqrt(n);
for (int i = 1; i <= n; i++) {
b[i] = (i - 1) / len + 1;
}
std::sort(q + 1, q + m + 1);
for (int L = 1, R = 0, i = 1; i <= m; i++) {
int l = q[i].l, r = q[i].r;
if (l == r) {
ansx[q[i].id] = 0;
ansy[q[i].id] = 1;
continue;
}
while(L > l) add(a[--L]);
while(L < l) del(a[L++]);
while(R > r) del(a[R--]);
while(R < r) add(a[++R]);
ansx[q[i].id] = res;
ansy[q[i].id] = query(y - x + 1);
}
for (int i = 1; i <= m; i++) {
long long d = std::__gcd(ansx[i], ansy[i]);
printf("%lld/%lld\n", ansx[i] / d, ansy[i] / d);
}
return 0;
}扩展
如果我们把块的大小设为 $\frac{n}{\sqrt{m}}$，那么莫队算法的复杂度为 $\mathcal O(n\sqrt m)$（复杂度分析同上）。
其实莫队还是可以支持单点修改的，详见「算法笔记」带修改莫队算法。