Moe's CF Life

喵~ 主人，今天我们来攻略一道来自 Codeforces 的有趣题目 (2123E - MEX Count) 吧！这道题看起来有点绕，但只要我们换个角度思考，就会发现它其实是一只温顺的小猫咪哦，喵~

题目大意

首先，我们要理解一个叫做 MEX 的概念。MEX (Minimum Excluded value) 指的是一个数组中没有出现过的最小非负整数。

举几个栗子🌰：

MEX([2, 2, 1]) = 0，因为 0 是最小的、没在数组里出现的非负整数。
MEX([3, 1, 0, 1]) = 2，因为 0 和 1 都在，但 2 不在。
MEX([0, 3, 1, 2]) = 4，因为 0, 1, 2, 3 都在，4 不在。

题目会给我们一个大小为 n 的数组 a。然后，对于每一个 k（从 0 到 n），我们需要回答一个问题：如果我们从数组 a 中恰好删除 k 个元素，新数组的 MEX 可能有多少种不同的值呢？

最后，我们需要输出 n+1 个整数，分别对应 k=0, 1, ..., n 的答案。

解题思路

直接去想“删除 k 个元素后 MEX 有多少种”会很麻烦，因为删除的组合太多了，脑子会变成一团乱麻的喵！(>ω<)

所以，我们不如换个思路，像小猫咪一样悄悄地从另一个方向接近猎物：对于一个固定的整数 m，它在什么条件下可以成为删除若干元素后的 MEX 呢？

要让 m 成为新数组的 MEX，必须满足两个条件：

所有比 m 小的非负整数（也就是 0, 1, ..., m-1）都必须存在于新数组中。
整数 m 本身必须不存在于新数组中。

我们来分析一下这两个条件对删除操作次数 k 的影响：

条件1的前置判断：要想让 0, 1, ..., m-1 存在于新数组，那么它们首先必须在原数组中就存在！如果原数组里连某个 i < m 都没有，那无论我们怎么删，i 都不会凭空出现，此时 MEX 最大也只能是 i，永远不可能达到 m。所以，我们可以先检查一下，如果 0 到 m-1 不是在原数组里都出现过，那么 m 以及所有比 m 大的数都不可能成为 MEX 了，可以直接停止对 m 的后续讨论。
确定删除次数 k 的范围：假设 0 到 m-1 在原数组中都存在，现在我们想让 m 成为 MEX。
- 为了满足条件2，我们必须把原数组中所有的 m 都删掉。设原数组中 m 的数量为 counts[m]，那么这 counts[m] 个元素是必须删除的。
- 为了满足条件1，我们必须为 0, 1, ..., m-1 中的每一个数，都至少保留一个。
那么，最少需要删除多少个元素呢？
- 最少删除数 (L)：我们必须删除所有的 m，也就是 counts[m] 个。对于 0 到 m-1，我们可以选择把它们的额外副本全留下，这样删除的就最少。所以最少删除 L = counts[m] 个元素。
最多可以删除多少个元素呢？
- 最多删除数 (R)：我们还是要删除所有的 m。同时，为了维持 0 到 m-1 的存在，我们每个数只留下一个，把它们多余的副本也全删了。除此之外，所有大于 m 的数也都可以删掉。总共需要保留的元素就是 0 到 m-1 各一个，共 m 个。原数组有 n 个元素，所以最多可以删除 R = n - m 个元素。
所以，只要 L <= R，对于任何一个介于 L 和 R 之间的删除次数 k（即 k ∈ [L, R]），我们都可以通过精巧地选择删除哪些元素，使得新数组的 MEX 恰好为 m。
这意味着，如果 m 是一个可能的 MEX 值，它会为删除次数 k 在 [counts[m], n-m] 这个区间内的所有情况，都贡献 1 个可能的 MEX 值。
最后的魔法：差分数组 我们现在的问题变成了：对于每个可能的 m，我们都找到了一个区间 [L, R]，要给这个区间里每个 k 的答案计数都 +1。如果对每个 m 都去遍历一遍 [L, R]，那也太慢了呀，喵~
这种对区间的批量加法操作，正是差分数组大显身手的时候！我们可以创建一个差分数组 diff。对于每个 m 产生的区间 [L, R]，我们只需要做两次操作：diff[L]++ 和 diff[R+1]--。当所有可能的 m 都处理完后，我们再对 diff 数组求一遍前缀和，就能得到每个 k 最终的答案了！是不是很优雅喵？

题解代码

这是解法的 C++ 实现，加了一些注释方便主人理解哦~

cpp

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

// 处理单个测试用例的函数喵
void solve() {
    int n;
    std::cin >> n;

    // 用一个 vector 来统计 0 到 n 每个数字出现的次数
    std::vector<int> counts(n + 1, 0);
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        if (x <= n) { // 题目保证了 a_i <= n，这里是个好习惯
            counts[x]++;
        }
    }

    // 这就是我们的差分数组 diff 啦！
    // diff[k] 记录的是 k 和 k-1 对应的答案数量的差值
    std::vector<long long> diff(n + 2, 0);

    // 检查 0, 1, ..., m-1 是否都在原数组中出现过
    bool prefix_ok = true;
    for (int m = 0; m <= n; ++m) {
        // 条件：要让 MEX = m，那么 0, 1, ..., m-1 必须都能保留下来
        // 这要求原数组中必须含有 0, 1, ..., m-1
        if (m > 0 && counts[m - 1] == 0) {
            prefix_ok = false;
        }

        if (!prefix_ok) {
            // 如果连 0..m-1 都凑不齐，那 m 和更大的数都不可能成为 MEX 了
            // 可以提前结束循环，喵~
            break;
        }

        // 如果 m 可以成为 MEX，那么需要删除的元素数量 k 在什么范围呢？
        // L: 至少要删除的。必须把所有的 m 都删掉。
        long long L = counts[m];
        // R: 至多能删除的。必须为 0..m-1 各留一个，总共留下 m 个。
        long long R = n - m;

        if (L <= R) {
            // 这说明 m 是一个有效的 MEX 候选。
            // 它可以为删除次数 k 在 [L, R] 范围内的所有情况都贡献一种可能性。
            // 我们用差分数组来标记这个区间。
            diff[L]++;
            diff[R + 1]--; // 在 R 的下一个位置减一，这样前缀和到 R 就结束了
        }
    }

    // 通过计算前缀和，从差分数组还原出每个 k 对应的答案
    long long current_mex_count = 0;
    for (int k = 0; k <= n; ++k) {
        current_mex_count += diff[k];
        std::cout << current_mex_count << (k == n ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

题目大意

解题思路

题解代码

相关知识点介绍

1. MEX (Minimum Excluded value)

2. 差分数组 (Difference Array)

题目大意 ​

解题思路 ​

题解代码 ​

相关知识点介绍 ​

1. MEX (Minimum Excluded value) ​

2. 差分数组 (Difference Array) ​

题目大意

解题思路

题解代码

相关知识点介绍

1. MEX (Minimum Excluded value)

2. 差分数组 (Difference Array)