“经典”问题 - 题解

标签与难度

标签: 前缀最小值, 后缀最小值, 预处理, MEX, 排列, 思维, O(n+m)

难度: 1600

题目大意喵~

主人你好呀~ 这道题是这样哒：

首先，我们有一个长度为 $n$ 的序列，它是一个 $0$ 到 $n-1$ 的全排列，喵。然后呢，会有 $m$ 次询问。每次询问会给出一个区间 $[l, r]$ ，我们需要找出这个区间里所有数字的 mex 值。

mex 是 "Minimum Excluded value" 的缩写，意思就是“最小的、没有出现过的非负整数”。举个栗子，对于集合 {1, 2, 4}，0 没出现，所以 mex 就是 0；对于集合 {0, 1, 3}，2 是最小的没出现的非负整数，所以 mex 就是 2。

这道题的特别之处在于， $n$ 和 $m$ 的规模都非常大，可以达到 $10^7$ 级别！所以我们需要一个超级高效的算法才行，不然就要超时啦~ 另外，输入数据（那个排列和所有的查询）都是在程序内部用一个特定的函数生成的，我们不需要自己处理复杂的输入，真好喵~

解题思路分析

看到区间查询问题，而且数据量这么大，暴力肯定是行不通的，对吧？如果我们每次查询都遍历一遍区间 $[l, r]$ ，那复杂度就是 $O(m \cdot n)$ ，肯定会慢得像只懒洋洋的猫咪在晒太阳。所以，我们必须利用预处理来加速查询，喵！

这道题有一个超级重要的线索，就是给定的序列是 $0$ 到 $n-1$ 的一个全排列！这意味着从 $0$ 到 $n-1$ 的每一个数字，都在序列里不多不少，正好出现一次。这个性质是解题的关键哦！

我们来想一下，一个数 $k$ 成为区间 $a[l..r]$ 的 mex，意味着什么呢？意味着 $0, 1, 2, \dots, k-1$ 这些数全都在区间 $a[l..r]$ 里，而 $k$ 这个数不在区间 $a[l..r]$ 里。

这个定义好像有点复杂。不如我们换个角度思考，喵~ mex 是最小的、不在区间里的非负整数。那哪些数字不在区间 $a[l..r]$ 里呢？因为整个序列是一个 $0$ 到 $n-1$ 的全排列，所以一个数字如果不在区间 $a[l..r]$ 里，那它一定在区间的外面！也就是在序列的前缀部分 $a[1..l-1]$ 或者后缀部分 $a[r+1..n]$ 里。

所以，所有不在区间 $a[l..r]$ 里的数字集合，就是前缀 $a[1..l-1]$ 和后缀 $a[r+1..n]$ 中所有元素的并集。

\text{不在 } a[l..r] \text{ 的数的集合} = \{ a_i \mid 1 \le i < l \} \cup \{ a_i \mid r < i \le n \}

mex 就是这个集合里的最小值！

\operatorname{mex}(a[l..r]) = \min(\{ a_i \mid 1 \le i < l \} \cup \{ a_i \mid r < i \le n \})

这个问题一下子就变得清晰起来了！我们只需要求出前缀 $a[1..l-1]$ 的最小值和后缀 $a[r+1..n]$ 的最小值，然后在这两个值里再取一个更小的，就是答案啦！

\operatorname{mex}(a[l..r]) = \min(\min_{1 \le i < l} a_i, \min_{r < i \le n} a_i)

这不就是前缀最小值和后缀最小值嘛！我们可以用 $O(n)$ 的时间预处理出它们，然后每次查询就能 $O(1)$ 搞定，是不是很棒？

具体操作步骤是这样哒：

预处理前缀最小值: 我们创建一个数组 prefix_min。prefix_min[i] 存储了原序列从第 1 个元素到第 $i$ 个元素的最小值。计算方式：prefix_min[i] = min(prefix_min[i-1], a[i])。边界条件：prefix_min[0] 可以设为一个非常大的数（比如 $n$ 或者更大），表示一个空前缀的最小值是无穷大。
预处理后缀最小值: 我们再创建一个数组 suffix_min。suffix_min[i] 存储了原序列从第 $i$ 个元素到第 $n$ 个元素的最小值。计算方式：从后往前遍历，suffix_min[i] = min(suffix_min[i+1], a[i])。边界条件：suffix_min[n+1] 也可以设为一个非常大的数。
回答查询: 对于每一个查询 $[l, r]$ ，我们想求的 mex 就是 min(prefix_min[l-1], suffix_min[r+1])。直接查表，瞬间出答案！

这样一来，总的时间复杂度就是 $O(n)$ 的预处理加上 $O(m)$ 的查询，总共是 $O(n+m)$ ，完美地解决了这个问题，喵~

代码实现

下面就是我根据这个思路精心准备的代码啦，加了详细的注释，希望能帮到你，呐！

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用 C++ 标准库的 std::min 和 std::max 会比手写快一点点哦
using namespace std;

// 题目给定的随机数生成器，我们直接用就好啦
unsigned int rd = 0;
inline int rnd(int mod, int seed) {
    rd ^= (1 << 13);
    rd ^= (rd >> 7);
    rd ^= (rd << 20);
    rd ^= (rd >> 3);
    rd ^= (rd << 10);
    rd ^= (rd << 5);
    rd ^= (1 << 2);
    return rd % mod + seed;
}

// 题目给定的序列生成函数
void make_sequence(vector<int>& arr, int n) {
    // iota 可以快速生成 0, 1, 2, ... 的序列
    iota(arr.begin() + 1, arr.end(), 0); 
    for (int i = 1; i <= n; ++i) {
        swap(arr[i], arr[rnd(n, 1)]);
    }
}

// 题目给定的查询生成函数
pair<int, int> make_query(int n) {
    int l = rnd(n, 1);
    int r = rnd(n + 1 - l, l);
    return {l, r};
}

const int MAXN = 10000000 + 10;
int p[MAXN];
int prefix_min[MAXN];
int suffix_min[MAXN];


int main() {
    // 为了更快的IO，虽然这题数据是内部生成的，但这是个好习惯喵~
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    scanf("%d%d", &n, &m);

    // 生成排列，注意我们用1-based索引，所以数组开大一点
    // vector<int> p(n + 2); // 直接用全局静态数组，避免动态分配大内存的开销
    for(int i = 1; i <= n; ++i) p[i] = i - 1;
    for (int i = 1; i <= n; ++i) {
        swap(p[i], p[rnd(n, 1)]);
    }

    // --- 核心预处理部分 ---

    // 1. 计算前缀最小值
    // prefix_min[i] = min(p[1], p[2], ..., p[i])
    // 边界 prefix_min[0] 设为一个比所有可能值都大的数
    prefix_min[0] = n; // n 就是一个很好的“无穷大”，因为所有元素都 < n
    for (int i = 1; i <= n; ++i) {
        prefix_min[i] = min(prefix_min[i-1], p[i]);
    }

    // 2. 计算后缀最小值
    // suffix_min[i] = min(p[i], p[i+1], ..., p[n])
    // 边界 suffix_min[n+1] 设为无穷大
    suffix_min[n+1] = n;
    for (int i = n; i >= 1; --i) {
        suffix_min[i] = min(suffix_min[i+1], p[i]);
    }

    // --- 查询处理部分 ---
    unsigned long long xor_sum = 0;
    for (int i = 0; i < m; ++i) {
        pair<int, int> query = make_query(n);
        int l = query.first;
        int r = query.second;
        
        // 查询区间 [l, r] 的 mex
        // 等于 min(p[1..l-1]的最小值, p[r+1..n]的最小值)
        int mex = min(prefix_min[l-1], suffix_min[r+1]);
        
        xor_sum ^= mex;
    }

    printf("%llu\n", xor_sum);

    return 0;
}

复杂度分析

时间复杂度: $O(n+m)$ ，喵~
- 生成排列 make_sequence 的时间复杂度是 $O(n)$ 。
- 预处理前缀最小值数组 prefix_min 需要一次遍历，时间复杂度 $O(n)$ 。
- 预处理后缀最小值数组 suffix_min 需要一次遍历，时间复杂度 $O(n)$ 。
- $m$ 次查询，每次查询都是 $O(1)$ 的常数时间操作。所以查询总时间是 $O(m)$ 。
- 加起来总共就是 $O(n+n+n+m) = O(n+m)$ 。对于 $10^7$ 的数据量来说，这是非常快的！
空间复杂度: $O(n)$ ，喵~
- 我们需要存储原始排列 p，大小为 $O(n)$ 。
- 存储前缀最小值的数组 prefix_min，大小为 $O(n)$ 。
- 存储后缀最小值的数组 suffix_min，大小为 $O(n)$ 。
- 总共占用的额外空间是 $O(n)$ 。

知识点总结

这道题虽然名字叫“经典”，但解法还是有点小巧思的，我们来总结一下学到了什么吧，喵~

MEX (Minimum Excluded value): 理解 mex 的定义是第一步。
利用问题特性: 本题最关键的一点就是利用了“序列是 $0$ 到 $n-1$ 的全排列”这一特性。看到排列、唯一性等条件，就要多想想这能带来什么便利。
逆向思维/问题转换: 直接求解“区间内最小的缺失数”比较困难，但把它转换成“区间外所有数的最小值”就豁然开朗了。这是解决算法问题时非常有用的一个技巧！
预处理: 对于多查询问题，如果查询本身不好优化，通常的思路就是预处理。通过牺牲一些空间和一次性的预处理时间，来换取每次查询的极速响应。
前缀/后缀信息统计: 前缀和、前缀积、前缀最大/最小值等是非常经典且强大的预处理工具，可以解决很多和区间相关的查询问题。这道题就是前缀/后缀最小值的完美应用场景。

希望这篇题解能帮助你更好地理解这道题！继续加油哦，主人！喵~

“经典”问题 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​