Crying 与 404 - 题解

标签与难度

标签: 主席树, 持久化线段树, 数据结构, 静态序列查询, 组合查询 难度: 2200

题目大意喵~

主人，你好呀~ Crying同学遇到了一个难题，需要我们帮忙的说！

事情是这样的：他有一个长度为 n 的数组 π，里面是 {0, 1, ..., n-1} 这 n 个数字的一个随机排列。 然后呢，他会进行 m 次询问。每次询问会给出三个数字 l, r, k。对于每一次询问，我们需要在由 π 数组下标从 l 到 r 的元素组成的集合 S = {π_l, π_{l+1}, ..., π_r} 中，找出不属于这个集合的、第 k 小的自然数（也就是 0, 1, 2, ... 这些非负整数啦）。

举个栗子！如果 π = {3, 0, 1, 4}，询问是 l=1, r=3, k=2。 那么集合 S 就是 {π_1, π_2, π_3}，也就是 {3, 0, 1}。 所有自然数中，不在这里面的数从小到大排队就是：2, 4, 5, 6, ... 第 1 小的是 2，第 2 小的就是 4 啦！所以这次询问的答案就是 4，喵~

解题思路分析

这道题看起来有点复杂，要从一个动态变化的集合里找第k小的缺失数字，真是让人头疼呢，喵~ 不过别担心，让我来一步步拆解它！

第一步：看穿问题的本质喵！

我们要求的“第 k 小的、不在集合 S = {π_l, ..., π_r} 中的自然数”，可以分成两种情况来考虑：

1. 这个缺失的数，本身就在 {0, 1, ..., n-1} 这个初始的数字集合里。
2. 这个缺失的数，比 n-1 还要大，也就是 {n, n+1, n+2, ...} 里面的数。

因为 π 是 {0, ..., n-1} 的一个排列，所以集合 {0, ..., n-1} 里的所有数，要么在查询区间 [l, r] 内，要么就在区间外。

设查询区间 [l, r] 的长度是 t = r - l + 1。 那么在 {0, ..., n-1} 这 n 个数中，有 t 个数出现在了 S 里。 因此，在 {0, ..., n-1} 中没有出现在 S 里的数的个数，就是 n - t 个。

这些 n - t 个数，肯定是比所有大于等于 n 的数要小的。所以它们就构成了“缺失数”序列的前 n - t 项。

第二步：处理两种情况

于是，我们的思路就清晰了，呐：

• 情况A：k > n - t 如果我们要找的第 k 小的缺失数，k 比 n-t 还大，那说明我们要找的数已经超出了 {0, ..., n-1} 的范围。 我们已经知道前 n - t 个缺失数都在 {0, ..., n-1} 里面了。那么第 n - t + 1 个缺失数，就是 n！第 n - t + 2 个就是 n+1，以此类推。 所以，第 k 个缺失的数就是 (n-1) 加上 k - (n-t)。 化简一下就是 n - 1 + k - n + t = k + t - 1。这里的 t = r - l + 1。 所以答案就是 k + (r - l + 1) - 1，这是一个简单的算术题，喵~

• 情况B：k <= n - t 这种情况就比较有趣了！我们要找的数，是在 {0, ..., n-1} 这个范围内的。 具体来说，我们要找的是在 {0, ..., n-1} 中，所有不属于 S = {π_l, ..., π_r} 的数里，第 k 小的那个。 哪些数不属于 S 呢？不就是那些在 π 数组里，但是下标在 [1, l-1] 或者 [r+1, n] 的数嘛！ 所以问题就转化成了：在 π 数组的 [1, l-1] 和 [r+1, n] 这两个不连续的区间里，所有数合在一起，第 k 小的值是多少？

第三步：请出我们的魔法道具——主席树！

对于这种“静态序列，区间第k小”的问题，有一个非常强大的数据结构，那就是主席树（也叫持久化线段树）！

主席树能做什么呢？它可以高效地查询一个数组任意前缀[1, i]中，数值在某个范围内的数的个数，或者第k小的值。

我们可以这样做：

1. 遍历原始的 π 数组，从 i = 1 到 n。
2. 对每个 i，我们都在 i-1 版本的主席树的基础上，插入 π_i 这个值，生成一个新的版本，也就是版本 i。
3. 版本 i 的主席树，就记录了 π 数组前 i 个数 {π_1, ..., π_i} 的数值分布情况。

建好了主席树，怎么解决我们刚才转化后的问题呢？ 我们要查询的集合是 {π_1, ..., π_{l-1}} ∪ {π_{r+1}, ..., π_n}。 这个集合可以看成是 (整个数组的数) - (区间 [l, r] 的数)。 但是这样不太好操作。更直接的方法是把两个部分加起来！

• {π_1, ..., π_{l-1}} 的数值分布，就记录在版本 l-1 的主席树里。
• {π_{r+1}, ..., π_n} 的数值分布，可以通过 (版本 n 的树) - (版本 r 的树) 来得到。

所以，我们想查询的集合的数值分布，可以由这三棵树组合而成：(版本 l-1) + (版本 n) - (版本 r)。 主席树的节点信息（比如 count）是满足可加减性的，所以我们可以把这三棵树的根节点传来传去，模拟一棵“虚拟树”的查询过程。

在这棵虚拟树上找第 k 小的值，就是一个标准的线段树上二分的过程啦！ 从根节点开始，我们看它虚拟的左子树包含了多少个数（count(l-1) + count(n) - count(r)）。

• 如果这个数量大于等于 k，说明第 k 小的数在左子树，我们就往左走。
• 否则，就往右走，并且把 k 减去左子树的数的数量。

这样一路走到底，就能在 $O(\log n)$ 的时间里找到答案啦！

总结一下我们的最终方案：

1. 对 π 数组建立主席树。
2. 对于每个查询 (l, r, k)：
   • 计算 t = r - l + 1 和 missing_in_perm = n - t。
   • 如果 k > missing_in_perm，答案是 k + t - 1。
   • 否则，利用版本 l-1, n, r 的主席树，查询组合集合中的第 k 小值。

是不是感觉思路一下子就通畅了呢？喵~

代码实现

下面是我根据这个思路，精心重构的一份代码，加了详细的注释，希望能帮到你哟！

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

// 快点快点，用上快速IO，不然要超时啦，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

// 主席树的节点，需要记录左右孩子和这个节点区间内的数字个数
struct Node {
    int left_child = 0;
    int right_child = 0;
    int count = 0;
};

const int MAXN = 500005;
// 主席树需要 N*logN 的空间，开大一点比较安心~
Node tree[MAXN * 25]; 
int roots[MAXN];      // 存储每个版本的根节点
int node_count = 0;   // 节点计数器
int n_val, m_queries; // n是排列大小，m是查询次数

// 在旧版本的基础上插入一个新值，并返回新版本的根节点
// current_root 是新版本的根，prev_root 是旧版本的
void insert(int& current_root, int prev_root, int val, int range_l, int range_r) {
    // 创建一个新节点，并从旧节点复制信息
    current_root = ++node_count;
    tree[current_root] = tree[prev_root];
    tree[current_root].count++;

    // 如果到达叶子节点，就返回
    if (range_l == range_r) {
        return;
    }

    int mid = range_l + (range_r - range_l) / 2;
    if (val <= mid) {
        // 值在左半边，递归到左子树
        insert(tree[current_root].left_child, tree[prev_root].left_child, val, range_l, mid);
    } else {
        // 值在右半边，递归到右子树
        insert(tree[current_root].right_child, tree[prev_root].right_child, val, mid + 1, range_r);
    }
}

// 在虚拟树上查询第k小的数
// root_l_minus_1, root_n, root_r 分别是版本 l-1, n, r 的树根
// 我们要找的是 (root_l_minus_1 + root_n - root_r) 这棵虚拟树上的第k小
int query_kth(int root_l_minus_1, int root_n, int root_r, int k, int range_l, int range_r) {
    // 到达叶子节点，这就是我们要找的数
    if (range_l == range_r) {
        return range_l;
    }

    // 计算虚拟左子树中元素的个数
    int left_count = tree[tree[root_l_minus_1].left_child].count +
                     tree[tree[root_n].left_child].count -
                     tree[tree[root_r].left_child].count;
    
    int mid = range_l + (range_r - range_l) / 2;
    if (k <= left_count) {
        // 第k小的数在左子树
        return query_kth(tree[root_l_minus_1].left_child, tree[root_n].left_child, tree[root_r].left_child, k, range_l, mid);
    } else {
        // 第k小的数在右子树，更新k的值
        return query_kth(tree[root_l_minus_1].right_child, tree[root_n].right_child, tree[root_r].right_child, k - left_count, mid + 1, range_r);
    }
}

int main() {
    fast_io();

    std::cin >> n_val >> m_queries;

    std::vector<int> pi(n_val + 1);
    // 建立主席树，版本0是空树
    roots[0] = 0;
    tree[0] = {0, 0, 0};

    // 题目中 π 的下标是 1 到 n，值为 0 到 n-1
    for (int i = 1; i <= n_val; ++i) {
        std::cin >> pi[i];
        // 基于上一个版本 roots[i-1] 插入新值 pi[i]，生成新版本 roots[i]
        insert(roots[i], roots[i - 1], pi[i], 0, n_val - 1);
    }

    for (int i = 0; i < m_queries; ++i) {
        int l, r;
        long long k; // k可能很大，用 long long
        std::cin >> l >> r >> k;

        int range_len = r - l + 1;
        int missing_in_perm_range = n_val - range_len;

        if (k > missing_in_perm_range) {
            // 情况A：要找的数大于 n-1
            long long ans = (long long)n_val + (k - missing_in_perm_range) - 1;
            std::cout << ans << "\n";
        } else {
            // 情况B：在 {0, ..., n-1} 范围内找
            // 查询 {π[1..l-1]} U {π[r+1..n]} 中的第k小
            int ans = query_kth(roots[l - 1], roots[n_val], roots[r], k, 0, n_val - 1);
            std::cout << ans << "\n";
        }
    }

    return 0;
}

复杂度分析

• 时间复杂度: $O((N+M) \log N)$

  • 建树: 我们需要遍历 N 个元素，每次插入操作在主席树上需要 $O(\log N)$ 的时间。所以建树的总时间是 $O(N \log N)$。
  • 查询: 我们有 M 次查询。对于每次查询，无论是简单的算术计算还是在主席树上查找第 k 小，都需要 $O(\log N)$ 的时间。所以所有查询的总时间是 $O(M \log N)$。
  • 总和起来就是 $O((N+M) \log N)$，对于 $N, M \le 5 \cdot 10^5$ 的数据规模来说，是完全可以接受的，喵~

• 空间复杂度: $O(N \log N)$

  • 主席树每次插入操作会创建 logN 个新节点。N 次插入后，总的节点数大约是 $N \log N$ 的量级。所以空间复杂度是 $O(N \log N)$。

知识点总结

这道题真是一次有趣的冒险，让我们收获了好多知识呢！

1. 问题转化: 解决复杂问题的关键一步，常常是把它分解成更简单、更熟悉的部分。我们把“找缺失数”转化成了“处理两种情况”，并把难点聚焦在“查询特定集合的第k小值”上，这就是解题的突破口！
2. 主席树 (Persistent Segment Tree): 这是一个非常强大的数据结构，是解决静态序列区间查询问题的利器。它的核心思想是保留每个历史版本，使得查询任意历史状态成为可能。
3. 树上信息的差分与合并: 主席树的美妙之处在于其节点信息的可加减性。我们可以通过 root[j] - root[i-1] 来得到区间 [i, j] 的信息。这道题更是展示了更灵活的组合方式 (root_A + root_B - root_C)，用来查询更复杂的集合，这个技巧非常值得学习，呐！

希望这篇题解能帮到你，如果还有不明白的地方，随时可以再来问我哦！一起加油，攻克更多的算法难题吧，喵~