莫队入门（1）-星游社区

基本概念与原理

核心思想：

莫队算法的核心是通过对区间询问进行巧妙排序和分块处理，实现对多个区间查询的高效求解。它利用了已经处理过的区间信息，避免了大量重复计算，从而达到优化时间复杂度的目的。

分块策略：

将长度为的序列划分为大小为的块。这种分块大小的选择是一种平衡，使得算法在时间复杂度上能达到较好的效果。

询问排序

- 先按照左端点所在的块进行排序，如果左端点在同一个块内，则按照右端点进行排序。这样排序的好处是在处理询问时，对于相邻的询问，指针移动的距离相对较小，能有效减少计算量。
- 例如，有一个长度为 10 的序列，分块大小为 3，那么会分成 4 块。对于询问区间【2，5】【4，7】【1，3】，【7，9】，排序后变为【1，3】【2，5】【4，7】【7，9】

算法实现步骤

分块操作：

计算块的大小，一般为。通过取余或除法运算确定每个元素属于哪个块。

询问排序：

按照上述规则对所有询问进行排序，通常可以自定义结构体并重载比较运算符来实现。

初始化：

设置初始的左右指针，一般初始化为一个空区间，如【1，0】，并初始化用于统计区间信息的数据结构，比如哈希表、数组等。

遍历询问：

对于每个询问，根据当前指针位置和询问区间，移动左右指针来调整区间。在移动指针的过程中，更新相应的区间统计信息。

输出答案：

根据处理完每个询问后得到的结果，输出最终答案。

常见应用场景

区间统计问题：

如统计区间内不同数字的个数、某个数字出现的次数等。例如，给定一个整数序列，有多个询问，每个询问要求计算给定区间内不同数字的数量。

区间最值问题：

可用于求解区间内的最大值、最小值等。不过，一般对于区间最值问题，如果有可持久化数据结构等其他更高效的方法，可能不会首选莫队算法，但在某些特定情况下莫队也能发挥作用。

区间颜色问题：

比如有一个颜色序列，每个位置有不同的颜色，询问区间内有多少种不同颜色的连续段等问题。

优化方法

奇偶优化：

对于询问的排序方式进行优化。当左端点所在块为奇数时，右端点升序排序；当左端点所在块为偶数时，右端点降序排序。这样可以减少指针在移动过程中的跨越次数，进一步提高算法效率。

带修莫队：

在莫队算法的基础上，支持对序列中的元素进行修改操作。通过引入时间维度，将修改操作和询问操作一起进行排序和处理，增加了算法的灵活性和适用性，但实现相对复杂一些。

回滚莫队：

当遇到一些不支持撤销操作的统计信息维护时，可以使用回滚莫队。它在处理询问时，对于左端点在同一块内的询问，采用特殊的处理方式，避免了对已经处理过的区间进行重复撤销操作，降低了时间复杂度。

代码示例：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <unordered_map>
using namespace std;

const int MAXN = 1e5 + 5;
int a[MAXN];
int block_size;

struct Query {
    int l, r, id;
    bool operator<(const Query& other) const {
        // 奇偶优化
        int block_l = l / block_size;
        int block_r = other.l / block_size;
        if (block_l!= block_r) return block_l < block_r;
        return block_l & 1? r < other.r : r > other.r;
    }
};

vector<Query> queries;
vector<int> answers;
unordered_map<int, int> count;

void add(int x) {
    if (count.find(x)!= count.end()) {
        count[x]++;
    } else {
        count[x] = 1;
    }
}

void remove(int x) {
    if (count.find(x)!= count.end()) {
        count[x]--;
        if (count[x] == 0) {
            count.erase(x);
        }
    }
}

int main() {
    int n, q;
    cin >> n >> q;
    block_size = sqrt(n);

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

    queries.resize(q);
    answers.resize(q);

    for (int i = 0; i < q; i++) {
        cin >> queries[i].l >> queries[i].r;
        queries[i].id = i;
    }

    sort(queries.begin(), queries.end());

    int l = 1, r = 0;
    for (const auto& query : queries) {
        // 移动指针并更新统计信息
        while (l > query.l) { l--; add(a[l]); }
        while (r < query.r) { r++; add(a[r]); }
        while (l < query.l) { remove(a[l]); l++; }
        while (r > query.r) { remove(a[r]); r--; }
        answers[query.id] = count.size();
    }

    for (int ans : answers) {
        cout << ans << endl;
    }

    return 0;
}