奇技淫巧：莫队算法

什么是莫队算法？

莫队算法（Mo's Algorithm）是一个由前国家队队长莫涛发明的，用于处理一系列 区间查询 问题的离线算法。它非常巧妙，本质上是一种“优雅的暴力”。

莫队算法适用于那些“从 [L, R] 的答案可以轻松（通常是 O(1)）地推导出 [L, R+1], [L, R-1], [L+1, R], [L-1, R] 的答案”的题目。例如，查询区间内不同元素的个数。

核心思想

莫队算法的核心思想是 离线处理 和 分块。

如果我们暴力处理 Q 个查询，每次都遍历区间，时间复杂度是 O(Q*N)。莫队算法通过改变查询的顺序，使得区间端点移动的总距离最小，从而优化时间复杂度。

1. 离线: 将所有的查询 (L, R) 存储下来，不按输入顺序处理。
2. 分块: 将原数组按大小为 sqrt(N) 分块。
3. 排序: 对所有查询进行重新排序。排序的规则是：
   • 如果两个查询的左端点 L 在 同一个块 ��，则按右端点 R 升序排序。
   • 如果左端点 L 在不同的块中，则按左端点 L 升序排序。
4. 暴力移动:
   • 维护两个指针 current_L 和 current_R，表示当前区间的左右端点。
   • 按照排好序的查询顺序，逐个回答查询。
   • 对于每个查询 (target_L, target_R)，我们将 current_L 和 current_R 一步步地移动到 target_L 和 target_R。
   • 在移动指针的过程中，实时更新答案。例如，如果 current_L 向右移动，就从当前答案中删除 array[current_L] 的贡献。

复杂度分析

为什么这样排序能优化时间？

• 右指针 R 的移动:

  • 对于左端点在同一个块内的所有查询，右指针 R 是单调递增的，所以在一个块内，R 最多移动 N 的距离。
  • 当左端点从一个块跳到下一个块时，R 最多从 N 跳回 1，也是 N 的距离。
  • 总共有 sqrt(N) 个块，所以右指针总的移动距离是 O(N * sqrt(N))。

• 左指针 L 的移动:

  • 在同一个块内，左指针 L 每次最多移动 sqrt(N) 的距离。
  • 当从一个块跳到下一个块时，左指针 L 最多也移动 2 * sqrt(N) 的距离。
  • 总共有 Q 个查询，所以左指针总的移动距离是 O(Q * sqrt(N))。

因此，莫队算法的总时间复杂度是 O(N * sqrt(N) + Q * sqrt(N))，在 N 和 Q 同阶时，可以看作 O(N * sqrt(N))。

C++ 伪代码

#include <vector>
#include <cmath>
#include <algorithm>

struct Query {
    int l, r, id, block;
};

bool compareQueries(const Query& a, const Query& b) {
    if (a.block != b.block) {
        return a.l < b.l;
    }
    return a.r < b.r;
}

// 全局变量用于维护当前区间的状态和答案
int current_ans = 0;
std::vector<int> counts;

void add(int index) {
    // 将 array[index] 加入区间
    // ... 更新 current_ans
}

void remove(int index) {
    // 将 array[index] 移出区间
    // ... 更新 current_ans
}

void mo_s_algorithm(std::vector<int>& arr, std::vector<Query>& queries) {
    int n = arr.size();
    int block_size = sqrt(n);
    for (int i = 0; i < queries.size(); ++i) {
        queries[i].block = queries[i].l / block_size;
        queries[i].id = i;
    }

    std::sort(queries.begin(), queries.end(), compareQueries);

    std::vector<int> answers(queries.size());
    int current_l = 0;
    int current_r = -1;

    for (const auto& q : queries) {
        while (current_l > q.l) { current_l--; add(current_l); }
        while (current_r < q.r) { current_r++; add(current_r); }
        while (current_l < q.l) { remove(current_l); current_l++; }
        while (current_r > q.r) { remove(current_r); current_r--; }
        answers[q.id] = current_ans;
    }
    // 输出 answers
}

莫队算法是一种将暴力美学发挥到极致的算法，在信息学竞赛中非常实用。它还有带修改、树上等多种变体。