C++莫队算法：暴力也能优雅

时间：2026-05-03 17:18:16 来源：作者：

在C++算法竞赛中，有一类问题让不少选手头疼：给定一个数组，多次询问某个区间内数字的出现次数、不同元素的个数、众数等信息。这类“区间离线查询”问题，如果直接暴力求解，每次查询 O(n)，总复杂度 O(n·q)，对于 n,q 在 1e5 的量级几乎不可行。而线段树或树状数组在面对“不同元素个数”这类不可减的信息时，又显得力不从心。直到莫队算法（Mo’s algorithm）的出现，才为这些问题提供了一款“优雅的暴力”——它用 O((n+q)·√n) 的时间，将看似棘手的区间统计问题变得简单而高效。

一、从暴力到“聪明”的暴力

假设我们有一个长度为 n 的数组 a，需要回答 q 个区间查询 [L, R] 中不同数值的个数。朴素做法是每个查询独立地用哈希表统计，每次 O(R-L+1)，最坏 O(nq)。但观察发现：相邻查询之间往往有重叠。如果我们能利用上一个查询的中间结果，只对区间端点进行微调，就能大幅减少重复计算。

莫队算法的核心思想就是：离线处理所有查询，通过排序和双指针移动，将总移动次数控制在 O(n√q) 级别。具体来说：

将数组分块，块大小一般取 B = n / sqrt(q) 或简单取 sqrt(n)。
对查询按照 左端点所在块 为第一关键字，右端点 为第二关键字排序（右端点在块内奇偶交替排序可以进一步优化）。
维护当前的区间 [curL, curR] 以及该区间内的统计信息（如 cnt 数组、答案变量）。
对于每个查询，将 curL 和 curR 一步步移动到目标区间，移动过程中更新统计信息。

整个过程看似还是“暴力移动”，但通过排序，所有查询的 curL 和 curR 移动总次数被控制在 O((n+q)·√n) 内，从而成为实用的算法。

二、算法详解与 C++ 实现

2.1 分块与排序

int n, q;
int a[N];
int pos[N];           // 每个位置所属的块编号
struct Query {
    int l, r, id;
} Q[N];

// 排序函数：先按块排，同块时右端点奇偶交替
bool cmp(const Query &a, const Query &b) {
    if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
    if (pos[a.l] & 1) return a.r > b.r;
    else return a.r < b.r;
}

块大小通常取 block = sqrt(n) 或 n / sqrt(q)，当然也可以直接取 300~500 的经验值。

2.2 区间移动与统计

我们维护一个 cnt[val] 数组，记录当前区间内每个值出现的次数，以及一个 curAns 表示当前区间内不同值的个数。

添加一个位置 x 时：

cnt[a[x]]++;
if (cnt[a[x]] == 1) curAns++;

删除一个位置 x 时：

cnt[a[x]]--;
if (cnt[a[x]] == 0) curAns--;

2.3 完整代码框架

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N], cnt[N], ans[N], curAns;
int n, q, block;

struct Query {
    int l, r, id;
} Q[N];

bool cmp(const Query &x, const Query &y) {
    if (x.l / block != y.l / block) return x.l / block < y.l / block;
    // 奇偶优化：右端点交替方向
    return ((x.l / block) & 1) ? (x.r > y.r) : (x.r < y.r);
}

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

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

int main() {
    scanf("%d", &n);
    block = sqrt(n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        scanf("%d%d", &Q[i].l, &Q[i].r);
        Q[i].id = i;
    }
    sort(Q + 1, Q + q + 1, cmp);
    
    int curL = 1, curR = 0;
    for (int i = 1; i <= q; 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 = 1; i <= q; i++) printf("%d\n", ans[i]);
    return 0;
}

三、复杂度分析

每个查询的移动量分为两部分：

左端点移动：在同一块内，左端点移动次数总和 O(√n)；切换块时，左端点最多移动 O(√n) 次，共 O(q·√n)？实际上，由于排序，左端点在同一块内的移动总量是 O(q·B) 吗？严谨分析：每个块内的左端点移动总量是 O(length_of_block · 该块查询次数)？更经典的分析是：左端点移动总次数 O(q·B)，右端点移动总次数 O(n·(n/B))。取 B = √n 时，两者均为 O(n√n)（假设 q ~ n）。若 q 远大于 n，可调整 B = n/√q。

事实上，标准莫队算法的复杂度为 O((n+q)·√n·f)，其中 f 是单次 add/remove 的复杂度（通常 O(1)）。