莫队算法：离线查询的“魔法排序”

引言

许多区间查询问题（如区间内不同数字个数、区间众数、区间逆序对等）如果用普通数据结构在线处理，往往需要复杂的线段树或树状数组。莫队算法 提供了一种巧妙的离线思路：将查询区间排序，通过两个指针在数组上不断移动，暴力地维护当前区间的答案。看似 O(n²) 的复杂度，经过精心排序（分块 + 按块排序）后，可以优化到 O((n+q)√n)。

如果普通暴力是“每次查询都从头跑到尾”，那么莫队就是 “带着两个游标，踩着轻快的舞步，在询问之间滑行” —— 它把相邻查询的重复计算降到了最低。

前置知识

核心思想

莫队算法适用于满足以下条件的区间查询问题：

• 可以离线处理。

• 在已知区间 [L, R] 的答案后，能较快地（通常 O(1) 或 O(log n)）转移到 [L-1, R]、[L+1, R]、[L, R-1]、[L, R+1]（即知道相邻区间的答案）。

算法步骤：

之所以按块排序，是为了让左指针在块内来回移动时，右指针单调递增，从而减少总移动次数。这就像在二维平面上给点排序，让路径呈“之”字形，总曼哈顿距离最小。

代码框架（以区间不同数字个数为例）

#include <bits/stdc++.h>
using namespace std;
const int N = 50005, M = 200005;

int a[N], cnt[N], ans[M], curAns;
int blockSize;

struct Query {
int l, r, id;
bool operator<(const Query &other) const {
int block_l = l / blockSize;
int block_other = other.l / blockSize;
if (block_l != block_other) return block_l < block_other;
// 奇偶优化：奇数块r升序，偶数块r降序
if (block_l & 1) return r < other.r;
else return r > other.r;
}
} q[M];

void add(int pos) {
int val = a[pos];
if (cnt[val] == 0) ++curAns;
++cnt[val];
}

void remove(int pos) {
int val = a[pos];
–cnt[val];
if (cnt[val] == 0) –curAns;
}

int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n;
blockSize = sqrt(n);
for (int i = 1; i <= n; ++i) cin >> a[i];
cin >> m;
for (int i = 0; i < m; ++i) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
}
sort(q, q + m);
int curL = 1, curR = 0;
curAns = 0;
for (int i = 0; i < m; ++i) {
int L = q[i].l, R = q[i].r;
while (curL > L) add(–curL);
while (curR < R) add(++curR);
while (curL < L) remove(curL++);
while (curR > R) remove(curR–);
ans[q[i].id] = curAns;
}
for (int i = 0; i < m; ++i) cout << ans[i] << '\\n';
return 0;
}

关键点：

• add 和 remove 操作需要根据问题定制，通常 O(1) 或 O(log n)。

• 奇偶优化：若左端点在同一块内，按右端点的奇偶性决定升序或降序，可以减少右指针来回移动的次数。

复杂度分析

设数组长度 n，查询数 q，块大小 B。

• 左指针移动：每个查询最多移动 B 次（在同一块内），不同块之间移动也是 O(n)。总左指针移动 O(q * B)。

• 右指针移动：在同一块内，右指针单调移动，每块最多 O(n)。总右指针移动 O((n/B) * n) = O(n² / B)。

• 总复杂度 O(q * B + n² / B)。取 B = n / √q 时最优，但通常取 B = √n 得到 O((n+q)√n)。

当 n,q 同阶时，复杂度约为 O(n√n)。

性质与注意事项

例题与解析

例题1：小Z的袜子（Luogu P1494）

题目描述
给定一个长度为 n 的数组（颜色），q 个查询，每个查询询问区间 [l, r] 内随机抽取两个数，它们颜色相同的概率（输出最简分数）。

输入示例

6 4
1 2 3 3 3 2
1 2
1 3
2 6
3 5

输出示例

0/1
1/3
8/15
2/5

解题思路

• 设区间内颜色 c 的数量为 cnt[c]，则相同颜色对数为 Σ C(cnt[c], 2) = Σ cnt[c]*(cnt[c]-1)/2。

• 总可能对数为 len*(len-1)/2，其中 len = r-l+1。

• 在 add 时，如果 cnt[val] 从 x 变为 x+1，相同颜色对数的增量 = [x*(x-1)/2 → (x+1)*x/2] 差值为 x。

• 在 remove 时，从 x 变为 x-1，差值减少 (x-1)。

• 维护当前答案分子 ans，每次查询得到 ans / total，并约分输出。

解析

• 经典的莫队入门题，注意约分时用 gcd。

• 利用组合数公式 O(1) 更新，总复杂度 O((n+q)√n)。

例题2：数颜色（Luogu P1903）

题目描述
带修改的区间不同颜色个数查询：支持单点颜色修改和区间查询。

输入示例

6 5
1 2 3 4 5 6
Q 1 3
R 1 2
Q 1 3
R 3 4
Q 2 5

输出示例

3
2
3

解题思路

• 带修莫队：增加一维时间 t，表示前 t 次修改已经应用。

• 将查询排序：左块、右块、时间（块大小通常取 n^{2/3}）。

• 移动指针时除了 L,R 还需移动时间指针，应用或撤销修改。

• 修改操作需要记录旧值，以便撤销。

解析

• 时间复杂度 O(n^{5/3})，适用于 n,q ≤ 10^5 左右。

• 实现细节：修改数组 color[x] = new，同时保存旧值；移动时间时判断当前 [L,R] 是否包含修改点，若包含则更新答案。

例题3：树上路径查询（Luogu SP10707）

题目描述
给定一棵树，每个点有颜色，多次询问树上两点路径上的不同颜色数。

输入示例

8 2
1 2 2 3 3 4 4 1
1 2
1 3
1 4
2 5
3 6
4 7
4 8
2 5
7 8

输出示例

3
3

解题思路

• 使用欧拉序将树转化为线性序列：每个节点在 DFS 序中出现两次（入栈和出栈）。

• 对于路径 (u, v)，设 first[u] <= first[v]，如果 LCA(u, v) = u，则区间为 [first[u], first[v]]；否则为 [out[u], first[v]]，并单独加上 LCA。

• 在区间中，出现两次的节点表示不在路径上，需要抵消。因此维护 vis 数组，遇到某个点时若未访问则添加，否则删除。

• 最后根据 LCA 是否被包含，决定是否额外添加 LCA 的颜色。

解析

• 树上莫队将树结构转化为线性结构，核心是处理“出现两次抵消”的 trick。

• 复杂度 O((n+q)√n)。

拓展

• 回滚莫队：适用于删除操作困难的问题（如区间众数），只支持添加，通过回滚到之前的版本。

• 莫队二次离线：进一步优化，将转移过程中的贡献也离线处理，适用于一些无法 O(1) 转移但能差分的题目。

• 在线莫队：利用分块+预处理实现在线查询（如“分块+预计算块间答案”）。

总结

莫队算法用简单暴力的思想，结合巧妙的离线排序，将许多区间查询问题的复杂度从 O(n²) 降至 O(n√n)。它不需要复杂的数据结构知识，却能在竞赛中解决大量题目，是“优雅的暴力”典范。