第96课 - 离线算法与莫队

1. 学习目标

通过本课的学习，你将能够：

理解离线算法（Offline Algorithm）的核心思想及其与在线算法（Online Algorithm）的区别。
掌握莫队算法（Mo's Algorithm）的基本原理，特别是其通过排序优化查询顺序的核心策略。
实现一个基础的莫队算法，用于解决静态序列上的区间查询问题。
分析莫队算法的时间复杂度，并理解其适用场景与限制。
了解莫队算法的常见变种及其在解决竞赛问题中的应用。

2. 核心概念

什么是离线算法？

简单来说，离线算法就是预先拿到所有需要处理的操作（或查询），然后一次性计算出所有答案。这与我们常见的在线算法（每次读入一个查询就立刻给出答案）形成对比。

想象你是一位老师，要批改学生的作业。

在线算法：学生交一份，你批改一份。
离线算法：你先把所有作业收上来，然后按照某个更高效的方式（比如按题目分类）统一处理。

离线算法的优势在于，它可以对输入数据进行全局的排序、分组等预处理，从而优化整体计算过程。莫队算法就是利用这一思想的经典例子。

莫队算法：排序与分块的魔法

莫队算法主要用于解决静态序列上的区间查询问题。一个经典问题是：“给定一个序列，多次询问区间 [l, r] 内有多少个不同的数？”

如果每次询问都从头扫描区间，复杂度是 O(n * m)（n为序列长度，m为查询次数），对于大规模数据无法接受。

莫队算法的思路很巧妙：

离线处理：将所有查询存起来。
排序优化：不按照输入的顺序处理查询，而是按照一种特殊规则排序，使得处理完一个查询 i 后，区间指针 [L, R] 移动到处理下一个查询 i+1 所需的平均移动步长变得很短。
滑动窗口维护信息：在移动指针 [L, R] 的过程中，动态维护一个数据结构（如计数数组），记录当前区间内的答案。

核心排序规则：

将序列分为若干个长度为 B (通常取 sqrt(n)) 的块。
对于一个查询 (l, r)，将 l 所在的块编号 pos = (l-1)/B 作为第一关键字。
将 r 作为第二关键字。
排序时，先按 pos 从小到大；pos 相同时，再按 r 从小到大排序（对于同一块内奇数块）或从大到小（对于偶数块，进一步优化）。

为什么这样排序高效？

同一块内：左端点 l 的移动距离被限制在块长 B 以内。右端点 r 在块内是单调递增（或交替递减）的，所以总移动距离约为 O(n)。
块与块之间：跨越块时，右端点 r 最多回跳 O(n)，但这种情况只有 O(n/B) 次。
总移动步长：可以证明，所有查询的左右指针总移动复杂度约为 O(n * sqrt(m)) 或 O(n * sqrt(n))，再乘以单次移动维护答案的 O(1) 开销，总复杂度为 O((n+m) * sqrt(n))，优于暴力法。

3. 代码示例

我们以“区间不同元素个数”问题为例，实现一个基础的莫队算法。

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

using namespace std;

const int MAXN = 30005; // 序列最大长度
const int MAXQ = 200005; // 最大查询次数

int arr[MAXN]; // 原始序列（已经过离散化）
int cnt[MAXN]; // 计数数组，cnt[x] 表示值 x 在当前区间出现的次数
int current_ans = 0; // 当前区间内不同数字的个数
int answers[MAXQ]; // 存储每个查询的答案

struct Query {
    int l, r, id; // 查询的左右端点和原始编号
    int block; // l 所在的块编号
} queries[MAXQ];

// 自定义排序函数
bool cmp(const Query &a, const Query &b) {
    // 先按块编号排序，再按右端点排序（偶数块内降序可优化，此处简化）
    if (a.block != b.block) return a.block < b.block;
    return a.r < b.r;
}

// 向区间中加入一个元素 x
void add(int x) {
    cnt[x]++;
    if (cnt[x] == 1) current_ans++; // 第一次出现，不同数字个数加1
}

// 从区间中移除一个元素 x
void remove(int x) {
    cnt[x]--;
    if (cnt[x] == 0) current_ans--; // 完全消失，不同数字个数减1
}

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

    int n, q;
    cin >> n;

    // 读入序列并进行离散化（处理值域大的情况）
    vector<int> temp(n);
    for (int i = 1; i <= n; ++i) {
        cin >> temp[i];
    }
    // 简易离散化
    vector<int> sorted_vals = temp;
    sort(sorted_vals.begin() + 1, sorted_vals.end());
    sorted_vals.erase(unique(sorted_vals.begin() + 1, sorted_vals.end()), sorted_vals.end());
    for (int i = 1; i <= n; ++i) {
        arr[i] = lower_bound(sorted_vals.begin() + 1, sorted_vals.end(), temp[i]) - sorted_vals.begin();
    }

    cin >> q;
    int block_size = (int)sqrt(n); // 块大小，通常取 sqrt(n)

    // 读入所有查询，并计算块编号
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
        queries[i].block = (queries[i].l - 1) / block_size; // 从0开始计数的块
    }

    // 对查询进行排序
    sort(queries, queries + q, cmp);

    // 莫队主过程：初始化当前区间为空 [0, 0]，然后通过移动指针处理所有查询
    int current_l = 1, current_r = 0; // 初始时区间为空
    for (int i = 0; i < q; ++i) {
        int l = queries[i].l, r = queries[i].r;

        // 移动左指针到目标位置 l
        while (current_l > l) {
            current_l--;
            add(arr[current_l]);
        }
        while (current_l < l) {
            remove(arr[current_l]);
            current_l++;
        }

        // 移动右指针到目标位置 r
        while (current_r < r) {
            current_r++;
            add(arr[current_r]);
        }
        while (current_r > r) {
            remove(arr[current_r]);
            current_r--;
        }

        // 当前区间 [l, r] 已就绪，记录答案
        answers[queries[i].id] = current_ans;
    }

    // 按原始顺序输出答案
    for (int i = 0; i < q; ++i) {
        cout << answers[i] << '\n';
    }

    return 0;
}

代码说明：

离散化：将原数组中的大数值映射到连续的 0, 1, 2...，以减小计数数组 cnt 的大小。
查询结构体：存储了查询的左右端点、原始编号（用于最后按顺序输出）和块编号。
排序：cmp 函数实现了核心的莫队排序规则。
add 和 remove：这两个函数是维护当前区间信息的核心，它们以 O(1) 的时间更新 current_ans。
主循环：按照排序后的顺序处理查询，通过 while 循环将当前的指针 [current_l, current_r] 移动到目标查询的 [l, r]，并利用 add/update 更新答案。

4. 实践练习

练习 1: 区间众数查询（基础）

题目描述：给定一个长度为 n 的序列和 m 次查询，每次查询一个区间 [l, r]，要求找出该区间内出现次数最多的那个数的出现次数（众数的出现次数）。输入：第一行两个整数 n, m，第二行 n 个整数表示序列，接下来 m 行每行两个整数 l, r。输出：对于每个查询，输出一行一个整数，表示该区间内众数的出现次数。要求：尝试使用莫队算法解决。你需要维护一个 cnt 数组（记录每个数出现的次数）和一个 freq 数组（freq[k] 表示出现次数为 k 的数有多少种），以及一个 max_freq 变量记录当前最大出现次数。思考在 add 和 remove 操作中如何更新这些信息。 预期输出：根据输入数据输出对应的众数出现次数。

练习 2: 带单点修改的莫队（进阶）

题目描述：在基础莫队问题之上，增加 m 次单点修改操作（例如，将位置 p 的值改为 val）。你需要回答 q 个查询，查询的是在考虑所有在该查询之前发生的修改后，区间 [l, r] 内的不同数字个数。输入：第一行两个整数 n, m（m 是修改和查询操作的总数）。第二行 n 个整数。接下来 m 行，每行格式为 1 l r（查询）或 2 p val（修改）。输出：对于每个查询，输出一行一个整数。提示：这是带修改的莫队（也称三维莫队）。你需要在查询结构体中增加一个时间戳 t，表示这是第几次操作后的状态。排序时，需要将时间戳作为第三关键字，或在移动区间指针的同时移动时间指针，进行“时间回溯”或“前进”。思考如何高效地应用和撤销修改。 预期输出：根据输入数据，在考虑相应时间点之前的修改后，输出查询结果。

5. 常见错误

排序规则写错：最常见的错误是排序函数没有正确实现“先按块，块内按右端点”的规则，特别是忘了处理同一块内左右端点顺序，或者对奇偶块的优化实现有误，导致效率退化。
指针移动边界问题：在 while 循环移动 current_l 和 current_r 时，初始条件和边界条件设置错误（例如，初始区间是 [1, 0] 而不是 [0, 0]），或者移动顺序不当（例如，先扩大再缩小可能造成重复计数或漏计）。
未考虑离散化：当序列的值域很大时（如 10^9），直接用值作为下标会内存溢出。必须先对序列进行离散化。
块大小选择不当：虽然通常取 sqrt(n)，但在某些情况下取 n/sqrt(q) 或根据数据范围手动调整可以获得更好的性能。选得太小或太大都会影响效率。
add/remove 函数逻辑错误：维护计数或最值信息时，更新逻辑不严谨，导致在多次操作后信息错误。例如，在维护众数时，更新 max_freq 的条件需要仔细考虑。

6. 小结

离线算法的核心是“预知未来”，通过预先获取所有操作并进行排序、分组等预处理，来摊销单次操作的复杂度。
莫队算法是离线算法的杰出代表，它通过将查询按 左端点所在块 和 右端点 的顺序排序，将所有查询的指针总移动距离优化到 O(n*sqrt(n)) 级别。
莫队算法的适用场景是静态序列上的区间查询问题，且单点更新和区间查询的维护操作可以高效进行（通常为 O(1) 或 O(logn)）。
莫队算法的变种包括带修改的莫队（三维莫队）、树上莫队（基于欧拉序）等，大大扩展了其应用范围。
莫队算法的优势在于实现相对简单，思维难度低于一些高级数据结构（如线段树、树状数组），且对于许多问题能提供优秀的性能。
其劣势在于只能处理离线问题，且对于强制在线的题目无能为力。同时，当维护操作（add/remove）的复杂度较高时，总复杂度可能不理想。

掌握莫队算法，能为你解决复杂的区间问题提供一把利器，尤其在算法竞赛中，它是一个非常实用且有趣的技巧。接下来，我们将学习另一个强大的离线算法——CDQ分治。

练习编辑器

rust