题目题解

问题理解

给定长度为 $n$ 的数组 $a$（元素值在 $[0, n]$ 之间）。
对于每个 $k = 0, 1, \dots, n$，统计从 $a$ 中恰好移除 $k$ 个元素后，剩余数组的 MEX 可能取值的个数。

---

第一步：原始 MEX

设 $m$ 为原数组的 MEX。即：

$$m = \operatorname{MEX}(a).$$

由于移除元素只能移除某些值，不能引入新值，因此剩余数组的 MEX 一定 $\le m$。
此外，MEX 不能超过剩余数组的长度。设剩余数组长度为 $n - k$，则

$$\text{MEX} \le n - k.$$

---

第二步：MEX 等于某个 $i$ 的条件

考虑 $0 \le i \le m$。
要使剩余数组的 MEX 等于 $i$，必须：

1. 所有小于 $i$ 的数在剩余数组中至少出现一次（这样 $i$ 才是最小的缺失值）。
2. 数字 $i$ 在剩余数组中不出现（因为缺失它）。

由于原数组中每个小于 $i$ 的数都至少出现一次（否则 $m \le i$），我们可以保留它们各一个。
要确保 $i$ 不出现，必须移除所有 $i$ 的实例。设 $\text{freq}(i)$ 为 $i$ 在原数组中的出现次数，则

$$k \ge \text{freq}(i).$$

此外，剩余数组长度为 $n - k$，其中我们已经保留了 $i$ 个不同的数（$0,1,\dots,i-1$），因此

$$n - k \ge i \quad \Rightarrow \quad k \le n - i.$$

所以 $i$ 可行的条件是：

$$\text{freq}(i) \le k \le n - i.$$

---

第三步：充分性证明

若上述条件成立，我们可以构造剩余数组如下：

• 从每个 $0,1,\dots,i-1$ 中保留一个元素（共 $i$ 个）。
• 从剩余元素（不包括 $i$）中任意选择 $n - k - i$ 个，保证总数达到 $n - k$。

由于 $\text{freq}(i) \le k$，我们移除了所有 $i$，且剩余元素足够多（因为 $n - k \ge i$），因此构造可行。

---

第四步：差分数组方法

设 $ans_k$ 为移除 $k$ 个元素后可能的 MEX 值的个数。

对于每个 $i$（$0 \le i \le m$），它对 $ans_k$ 的贡献是：当 $k$ 在区间 $[\text{freq}(i), n - i]$ 内时，$i$ 是可行的。

因此我们可以用差分数组 $diff$ 来统计：

• 在 $k = \text{freq}(i)$ 处 $+1$（开始可行）
• 在 $k = n - i + 1$ 处 $-1$（结束可行）

初始 $diff$ 全为 $0$。
对所有 $i = 0, 1, \dots, m$ 执行：

$$diff[\text{freq}(i)] \mathrel{+}= 1, \quad diff[n - i + 1] \mathrel{-}= 1. $$

然后前缀和得到 $ans_k$：

$$ans_k = \sum_{j=0}^k diff[j].$$

注意 $i > m$ 时，由于原数组中缺少 $m$，不可能使 MEX 大于 $m$，因此不考虑。

---

最终算法

1. 统计每个值的出现次数 $\text{freq}[v]$。
2. 找到原数组的 MEX $m$（最小的未出现值）。
3. 初始化差分数组 $diff$ 长度为 $n+2$。
4. 对 $i = 0$ 到 $m$：
   • $diff[\text{freq}[i]] \leftarrow diff[\text{freq}[i]] + 1$
   • $diff[n - i + 1] \leftarrow diff[n - i + 1] - 1$
5. 计算前缀和得到 $ans_0, \dots, ans_n$，并输出。

---

时间复杂度

• 统计频率：$O(n)$。
• 处理 $m+1$ 个 $i$：$O(m)$。
• 总复杂度 $O(n)$，满足 $\sum n \le 2\times 10^5$。

---

代码实现

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    vector<int> freq(n + 1, 0);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] <= n) freq[a[i]]++;
    }
    
    // 找到原数组的 MEX
    int mex = 0;
    while (freq[mex] > 0) mex++;
    
    // 差分数组
    vector<int> diff(n + 2, 0);
    for (int i = 0; i <= mex; i++) {
        diff[freq[i]]++;
        diff[n - i + 1]--;
    }
    
    // 前缀和得到答案
    vector<int> ans(n + 1, 0);
    int cur = 0;
    for (int k = 0; k <= n; k++) {
        cur += diff[k];
        ans[k] = cur;
    }
    
    // 输出
    for (int k = 0; k <= n; k++) {
        cout << ans[k] << (k == n ? "\n" : " ");
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

验证样例

对于第一个测试用例：

• $n=5$, $a = [1,0,0,1,2]$
• $\text{freq}[0]=2$, $\text{freq}[1]=2$, $\text{freq}[2]=1$, $\text{freq}[3]=0$ → $m=3$
• 对 $i=0$: $diff[2]++$, $diff[5-0+1=6]--$
  对 $i=1$: $diff[2]++$, $diff[5-1+1=5]--$
  对 $i=2$: $diff[1]++$, $diff[5-2+1=4]--$
  对 $i=3$: $diff[0]++$, $diff[5-3+1=3]--$

计算前缀和得到： $ans = [1, 2, 4, 3, 2, 1]$，与样例一致。

---

总结

本题的关键在于：

1. 将问题转化为对每个 $i$ 判断 $k$ 的可行区间 $[\text{freq}(i), n-i]$。
2. 使用差分数组高效维护 $ans_k$ 的变化。
3. 注意 MEX 不能超过原始 MEX 和剩余数组长度。