引言许多区间查询问题如区间内不同数字个数、区间众数、区间逆序对等如果用普通数据结构在线处理往往需要复杂的线段树或树状数组。莫队算法提供了一种巧妙的离线思路将查询区间排序通过两个指针在数组上不断移动暴力地维护当前区间的答案。看似 O(n²) 的复杂度经过精心排序分块 按块排序后可以优化到 O((nq)√n)。如果普通暴力是“每次查询都从头跑到尾”那么莫队就是“带着两个游标踩着轻快的舞步在询问之间滑行”—— 它把相邻查询的重复计算降到了最低。前置知识离线查询先读入所有查询经过排序处理后统一回答。分块Block将数组分成大小约 √n 的块。双指针L和R指向当前维护的区间每次通过移动指针来添加或删除元素更新答案。复杂度分析指针移动总次数 O((nq)√n)。核心思想莫队算法适用于满足以下条件的区间查询问题可以离线处理。在已知区间[L, R]的答案后能较快地通常 O(1) 或 O(log n)转移到[L-1, R]、[L1, R]、[L, R-1]、[L, R1]即知道相邻区间的答案。算法步骤将数组分成块大小为B √n或n / √q优化。将所有查询按照(L / B, R)排序首先按左端点所在的块编号升序如果块编号相同则按右端点升序对于奇数块可降序即奇偶优化。初始化curL 1, curR 0当前答案ans 0。依次处理每个查询(qL, qR)移动curL到qL每次移动时删除或添加元素。移动curR到qR。记录当前答案。输出所有答案按原顺序。之所以按块排序是为了让左指针在块内来回移动时右指针单调递增从而减少总移动次数。这就像在二维平面上给点排序让路径呈“之”字形总曼哈顿距离最小。代码框架以区间不同数字个数为例#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((nq)√n)。当 n,q 同阶时复杂度约为 O(n√n)。性质与注意事项特性说明离线必要莫队必须提前知道所有查询不能在线处理顺序敏感答案仅依赖于区间内容与顺序无关支持修改带修莫队增加时间维度可处理单点修改复杂度 O(n^{2/3}·q^{2/3})树上莫队将树转化成欧拉序转化为区间问题常数优化使用while循环顺序固定、奇偶优化、调整块大小例题与解析例题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-l1。在add时如果cnt[val]从 x 变为 x1相同颜色对数的增量 [x*(x-1)/2 → (x1)*x/2]差值为 x。在remove时从 x 变为 x-1差值减少(x-1)。维护当前答案分子ans每次查询得到ans / total并约分输出。解析经典的莫队入门题注意约分时用gcd。利用组合数公式 O(1) 更新总复杂度 O((nq)√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((nq)√n)。拓展回滚莫队适用于删除操作困难的问题如区间众数只支持添加通过回滚到之前的版本。莫队二次离线进一步优化将转移过程中的贡献也离线处理适用于一些无法 O(1) 转移但能差分的题目。在线莫队利用分块预处理实现在线查询如“分块预计算块间答案”。总结莫队算法用简单暴力的思想结合巧妙的离线排序将许多区间查询问题的复杂度从 O(n²) 降至 O(n√n)。它不需要复杂的数据结构知识却能在竞赛中解决大量题目是“优雅的暴力”典范。