莫队算法：把区间查询离线化

问题背景

给定一个长度为 n 的数组，给定 m 个询问，每个询问问：”区间 [l, r] 内有多少个互不相同的数？”

n, m 都是 10^5 量级。

最朴素的解法是：对每个询问，把 [l, r] 扫一遍，用一个 vis[] 数组去重。复杂度 O(nm)，也就是 10^10 次操作，必挂。

第二反应是上线段树。但仔细想会发现：“区间不同元素个数”这个信息没法在线段树上 O(log n) 合并。你没法从左右两个儿子的”不同元素个数”推出来（因为可能有重复元素在两边都被数过）。所以线段树走不通。

这时候就该请出今天的主角了。

思路

第一步：核心洞察——移动端点的代价极低

先做一个关键的能力假设：我们能在 O(1) 时间内让”当前维护的区间”多包含一个元素或少包含一个元素，并且 O(1) 同步更新答案。

对”区间不同元素个数”，这非常容易：

// 把位置 p 加入当前区间
void add(int p) {
    if (cnt[a[p]]++ == 0) ++distinct;   // 从 0 变 1，不同元素个数才增加
}
// 把位置 p 移出当前区间
void del(int p) {
    if (--cnt[a[p]] == 0) --distinct;   // 从 1 变 0，才算减少
}

有了这个能力，处理单个询问就是：从空区间出发，把 L 指针移到 l、R 指针移到 r，答案就是 distinct。

关键在于：处理完询问 (l₁, r₁) 后，处理 (l₂, r₂) 并不需要从头再来，只要从当前指针位置继续移动即可。这就是莫队的全部思想。

于是总复杂度取决于一个纯粹的问题：怎样排序 m 个询问，使 L、R 两个指针的总移动次数最少？

第二步：朴素的失败——按输入顺序处理

如果按询问的输入顺序处理，构造一个反例：

n = 10^5，考虑询问交替为 [1, 2]、[n-1, n]、[1, 2]、[n-1, n]……

每处理一次，L 指针就要从 1 跳到 n-1，再跳回来。总移动次数是 O(nm)，和朴素解法没区别。

结论：必须离线重排询问顺序。

第三步：莫队的排序——两个关键字

莫队的经典排序规则：

关键字一：左端点 L 按块划分，块内按 R 递增。

设块长 B。把所有下标按长度 B 分块：belong[i] = (i - 1) / B。询问按 (belong[l], r) 排序。

直觉解释：把左端点”粗粒度”地归类。同一个块内的 L 位置很接近（最多差 B-1），所以块内处理时 L 最多来回抖 B 次；而 R 是单调递增的，一趟扫到底 n 次。

跨块时 L 会跳，但块数只有 n/B 个，跳的总代价是 O(n²/B) 量级（每块一次跳）。

为什么块长取 √n？ 平衡两项（详细推导见下一节）：块内 L 的抖动是 O(mB)，R 在每块内单调递增扫过全局是 O(n²/B)。对 B 求最小值 → B = n/√m。

当 n 和 m 同阶时，B = √n，总复杂度 O(n√n)，这就是大家常说的 O(n√m)。

关键字二：奇偶块优化（蛇形排序）。

上面说的还有一个常数浪费：相邻两块的 R 都从小到大，导致块与块的交界处 R 会折返。

举例：块 1 最后一个询问是 [1, 5000]，块 2 第一个询问是 [5001, 5002]。R 从 5000 跳回 5002，看似只差 2。但换成块 1 最后一个询问是 [1, 100]、块 2 第一个是 [5001, 9999]，R 就从 100 跳到 9999，白走 9899 步。

解决办法：奇偶块交替排序方向。

• 偶数块（belong 为偶数）：R 递增
• 奇数块：R 递减

这样相邻块的 R 值域总是首尾相接，交界处的折返被消掉了。实测能省下约 1/3 到 1/2 的常数。这是一行代码的代价：

if (a.belong != b.belong) return a.belong < b.belong;
return (a.belong & 1) ? (a.r > b.r) : (a.r < b.r);

第四步：指针移动次数与复杂度推导

我们严格数一下指针移动次数。

设块长 B，块数 T = ⌈n/B⌉，询问数 m。

R 指针总移动：

• 块内：R 单调，块内 R 的移动量 ≤ n，共 T 块 → O(Tn) = O(n²/B)
• 块间：奇偶排序后，折返被抑制，额外代价 O(n) 量级，可忽略
• 合计：O(n²/B)

L 指针总移动：

• 块内：L 只在块内抖动，每次 |ΔL| ≤ B，块内最多 m 次 → O(mB)
• 块间：跳到下一个块，|ΔL| ≤ 2B + 跳块距离，跳块总代价 O(n)（从块 1 跳到块 T 共 n）
• 合计：O(mB + n)

总时间：O(n²/B + mB)，每次移动 O(1) 更新。

取 B = n/√m（实践中 B = max(1, n / (int)sqrt(m)) 或直接 sqrt(n)），得：

O(n√m + m)

这就是莫队 O(n√m) 的严格来源。注意它是 O(n√m) 而不是 O((n+m)√n)——前者更准确。

注意复杂度依赖于”每次移动 O(1)”这个前提。 这是莫队的核心限制，下面第四节会讲。

第五步：回滚莫队——当”删除”很贵时

有一个问题：如果一个元素被删除后很难 O(1) 撤销呢？

经典反例：区间众数。维护一个 cnt[] 数组和”最大 cnt”答案。如果删掉一个元素使 cnt[v] 从 3 降到 2，答案 3 就失效了，而正确答案可能是另一个值的 3。要重新求最大值，需要遍历所有不同的值，那是 O(不同值个数)。

莫队的标准技巧此时失效。 回滚莫队（Rollback Mo / 不删除莫队）的思路是：

只允许”添加”，不允许”删除”，用回滚代替删除。

具体做法：

1. 把询问按右端点分块（注意：这次是 R 分块，不是 L），块内按 L 递增排。
2. 处理一个块之前，把指针重置到该块的右边界，区间为空。
3. 然后按 L 从大到小处理块内询问：每次先临时把 L 往右扩展到 l（只增），读答案，再把 L 回滚回块左边界（撤销刚才的扩展）。
4. 这样”撤销”永远是一段连续区间的整体丢弃，代价 O(B)，而不是逐个删除。

关键洞察：回滚莫队是把”删除操作”替换为”记录改动前状态，恢复现场”。 恢复现场总是容易的——最难的是”部分删除”。

复杂度：O(n√m)，但常数比普通莫队大一倍（要来回扩展+回滚）。

适用场景：区间众数、树上路径众数等”答案不可回退”的问题。

第六步：带修莫队——把时间作为第三关键字

如果题目还带修改操作（单点赋值），二维的 (L, R) 就不够了。

考虑：询问 (l, r, t) 问的是”执行完前 t 次修改后，区间 [l, r] 的答案”。

朴素想法是给每个询问单独跑一遍，O(mn)。

带修莫队（修改莫队）的做法：把时间 t 升维成第三维指针。

排序关键字变成三个：

1. L 所在块（左端点分块）
2. R 所在块（右端点分块，注意这次也分块）
3. 块内先按 t 递增，再按 r 递增（蛇形）

维护三个指针 L, R, T：

• T 增大：执行下一条修改（前进）
• T 减小：撤销上一条修改
• L、R 移动：正常增删元素

为什么时间指针能”撤销”？ 因为修改操作必须是可逆的：单点赋值 a[p] = v 的逆操作就是 a[p] = 原来的值。只要额外记录每条修改的原值，就能 O(1) 回退。

复杂度推导：三维分块，两个维度分块，时间维度不划分块。

• L 移动：O(mB)
• R 移动：O(mB)
• T 移动：O(q · (n/B)²) = O(q n²/B²) —— T 在每个 (L块, R块) 组合内单调
• 合计 O(mB + q·n²/B²)，取 B ≈ n^(2/3) → O(n^(5/3))（n、q 同阶时）

这是带修莫队比普通莫队慢不少的原因，也是它只在”修改多、且修改本身难以在线处理”时才用的原因。

限制：带修莫队要求修改可逆。区间赋值、区间加（可逆，因为减去即可）都行；但”随机赋值且不保留原值”这种就不可逆，必须改造。

第七步：莫队 vs 线段树，怎么选

莫队不是万能的，判据其实很清楚：

选莫队的条件（三个都要满足）：

1. 区间支持 O(1) 的加入/删除
2. 答案可以 O(1) 增量维护
3. 题目允许离线（无强制在线）

选线段树/其他数据结构的情况：

• 答案需要复杂合并：如区间和（虽然莫队也能做，但线段树 O(m log n) 优于 O(n√m)，当 m ≪ n 时差别巨大）。记住：n = 10^6, m = 100 时，莫队的 O(n√m) = 10^7，反而不如线段树的 m log n = 10^3。 莫队的复杂度里有那个 n，n 大而 m 小时它不划算。
• 需要真正的”删除”且删除不可逆：区间众数 → 回滚莫队或线段树维护最值。
• 强制在线：题面出现 ^ last_ans 就不能排序询问，莫队直接失效。
• 有修改：普通莫队失效，考虑带修莫队，或直接上树套树/时间线段树。

一句话判断：先看 n 和 m 谁大。 m 远小于 n → 线段树；n 和 m 同阶 → 莫队。

正确性

以”离线区间求不同元素个数”为例：

引理 1（指针状态正确性）：每次循环结束时，维护的区间恰为当前询问的 [l, r]，且 distinct 等于该区间内不同元素的个数。

证明：初始 L=1, R=0 表示空区间，distinct = 0，成立。调整指针时用 while + add/del 逐步移动，移动一格对应加入或移除一个位置。由引理 2，每一步 add/del 都保持 distinct 正确。循环终止时 L==l 且 R==r，故结论成立。

引理 2（add/del 的正确性）：cnt[v] 记录当前区间内 v 的出现次数。加入一个 v 时，只有 cnt[v] 由 0 变 1 才使不同元素个数 +1；移出一个 v 时，只有 cnt[v] 由 1 变 0 才使个数 -1。

这是定义直接给出的显然结论。

定理（整体正确性）：算法输出的每个答案都是对应询问的正确答案。

证明：由引理 1，处理询问 i 时 distinct 恰为 [l_i, r_i] 的不同元素个数。ans[i] = distinct 即正确答案。而排序只改变处理顺序，不改变任何询问的内容，最终按原下标 id 存回答案，输出顺序与输入顺序一致。

关于排序不影响正确性：莫队的正确性完全依赖”排序只是换顺序，不改答案”。这是它能被离线使用的前提，也正是它不能用于强制在线题的原因。

复杂度

设块长 B，询问数 m，修改次数 q，数组长 n。

算法	排序关键字	复杂度
朴素	无	O(nm)
普通莫队	belong(l), r（奇偶块）	O(n²/B + mB) → O(n√m)
回滚莫队	r 所在块, l	O(n√m)，常数更大
带修莫队	belong(l), belong(r), t, r	O(mB + q·n²/B²) → O(n^(5/3))
线段树	在线	O(m log n)，n 大 m 小时更优

空间：莫队 O(n + m)，只需存数组和询问，比线段树的 O(n) 多但数量级相当。

参考代码（C++17）

离线区间求不同元素个数（可直接提交，CSP-S 级莫队模板）：

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int n, m;
int a[100005];              // 数组，a[1..n]
int cnt[100005];            // cnt[v] = 值 v 在当前区间内出现的次数
int distinct_cnt;           // 当前区间内不同元素的个数

// 把位置 p 加入当前区间
inline void add(int p) {
    // cnt 先自增：若自增前为 0，说明这个值此前不在区间内
    if (cnt[a[p]]++ == 0) ++distinct_cnt;
}

// 把位置 p 移出当前区间
inline void del(int p) {
    // cnt 先自减：若自减后为 0，说明这个值已经不在区间内了
    if (--cnt[a[p]] == 0) --distinct_cnt;
}

struct Query {
    int l, r, id, block;    // 询问左右端点、原编号、l 所在块号
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // 块长取 sqrt(n)。注意要保证 >= 1，防止 n=0 或极端情况
    int B = max(1, (int)sqrt(n));

    vector<Query> qs(m);
    for (int i = 0; i < m; ++i) {
        cin >> qs[i].l >> qs[i].r;
        qs[i].id = i;                        // 记住原编号，用于按输入顺序输出
        qs[i].block = (qs[i].l - 1) / B;     // 左端点所在块
    }

    // 莫队排序：关键字一是 l 所在块升序；关键字二是块内 r 递增
    // 奇偶块优化：奇数块让 r 递减（蛇形），消除块间 R 折返的常数损失
    sort(qs.begin(), qs.end(), [](const Query& x, const Query& y) {
        if (x.block != y.block) return x.block < y.block;
        if (x.block & 1) return x.r > y.r;
        return x.r < y.r;
    });

    vector<int> ans(m);

    int L = 1, R = 0;   // 初始区间为空（注意 L > R 表示空）
    distinct_cnt = 0;

    for (const Query& q : qs) {
        // 移动顺序非常重要：先"把区间撑大"，再"把区间缩小"
        // 如果先收缩 L，而目标 L 在当前区间右侧，那些位置从未被加入过，
        // del() 会让 cnt 变成负数，答案就彻底错了
        while (L > q.l) add(--L);   // 左端点左移：加入新位置
        while (R < q.r) add(++R);   // 右端点右移：加入新位置
        while (L < q.l) del(L++);   // 区间已足够大，再收缩左端点：移除旧位置
        while (R > q.r) del(R--);   // 收缩右端点：移除旧位置

        ans[q.id] = distinct_cnt;
    }

    for (int i = 0; i < m; ++i) cout << ans[i] << '\n';
    return 0;
}

移动顺序为什么是这样？ 先扩后缩，保证 L 和 R 交叉时区间始终有效（不会出现”删除一个从未加入的位置”，那会让 cnt 变成负数）。这与线段树的 pushdown 是同一类”维护不变量”的问题。

易错点清单

1. 忘记 cnt 初始化为 0。 全局数组会自动初始化，但改成局部 vector 时必须显式 assign(n+1, 0)。
2. distinct 的更新时机写错。 cnt[a[p]]++ == 0 判断的是自增前的值，必须用后置自增配合前置判断；写成 ++cnt[a[p]] == 1 也对，但写成 cnt[a[p]] == 0 后再自增的顺序如果和 del 不对称就会出错。
3. L、R 移动顺序搞反导致负数下标。 用 while (L > q.l) add(--L); while (L < q.l) del(L++); 的”先扩后缩”写法。
4. 块长 B 取 0。 sqrt(n) 在 n = 1 时是 1，不会有问题，但用 (int)sqrt(m) 时要注意至少 1。统一写 max(1, ...)。
5. 忘了记录原编号 id。 排序后询问顺序变了，直接输出就错序了。
6. 奇偶块优化写反。 block & 1 为奇数时 r 递减。写反了不会错（复杂度还在），但会失去常数优势——不过一定要确认代码里确实用了当前块的奇偶性而不是询问的。
7. 暴力退化：所有询问都按 r 递减但都在同一块内，此时等价于没优化，问题不大；但如果你把 belong 关键字漏了，退化成 O(nm)。
8. 带修莫队里撤销修改时忘了保存原值。 修改结构体必须含 pre 字段记录修改前的值。
9. 带修莫队的 t 指针移动时，t 的含义是”已执行的修改条数”。 用 t <= q.t / t > q.t 控制时注意闭开区间，建议统一用”当前已执行前 t 条修改”，即 while (t < q.t) change(++t); while (t > q.t) rollback(t--);
10. 强制在线的题套莫队。 遇到 ^ last_ans 必须换方案，莫队排序会直接破坏解码。

常见误区

误区一：”莫队是万能的区间查询算法。”
莫队的前提是”加入/删除 O(1) 且答案可增量维护”。如果答案是区间众数、或者需要复杂合并，莫队就失效了（要用回滚莫队）。更重要的是——莫队的复杂度里有 n，n 大 m 小的时候它比线段树慢得多。

误区二：”莫队只是把询问排序，没什么难的。”
排序规则是简单的，难点在于你能不能想出”加入/删除 O(1)”的那个辅助数组。这才是莫队的真正门槛。排序只是水到渠成。

误区三：”带修莫队比普通莫队更优，能用就用。”
带修莫队的复杂度是 O(n^(5/3))，n 很大时反而不如普通莫队。只有当修改本身无法在线处理（比如修改影响大量元素）时才用带修。

误区四：”回滚莫队是带修莫队的特例。”
两者不同：回滚莫队处理的是”删除贵”的问题，用的是”允许撤销、避免部分删除”的技巧；带修莫队处理的是”多了时间维度”的问题。思路相似但目的不同。

---

一句话总结：莫队的本质是”用离线排序换取端点移动次数的最小化”。判断能不能用，只问一句——「加入一个元素和删除一个元素，能不能 O(1) 更新答案？」能，就是莫队；不能，就该考虑回滚莫队或者换数据结构。