CF2123E 题解

· · 题解

这题真比 CD 简单吧。

直接求是比较困难的，我们考虑换个角度。

考虑枚举 \operatorname{MEX} 为 0,1,2,\dots,n 的情况能通过删几个数来达成，然后加到答案数列里。

以样例的第一组数据举例。

5
1 0 0 1 2

我们假定答案数列都先为 0。

当 \operatorname{MEX} = 0 时，可以删除 0 0，1 0 0，0 0 1，0 0 2，1 0 0 1，1 0 0 2，0 0 1 2，1 0 0 1 2。删除 2，3，4，5 个数字都可以得到，所以答案数列的第 2 到 5 位分别增加 1。后面以此类推。

接着我们有定理：不论 \operatorname{MEX} 为多少，“通过删除若干数字来达成该 \operatorname{MEX}”中删去数字的数量组成的集合是连续的。

就如上面的“删除 2，3，4，5 个数字都可以得到”中的 2，3，4，5 都是连续的。

考虑证明。

假设当前的 \operatorname{MEX} = x。

根据 \operatorname{MEX} 的定义，数列中 0 到 x - 1 的数量都必须 \ge 1，而数列中不能有 x。

这说明所有 x 都是必删的，而数列中的 0 到 x - 1 都是只有一个是不可删的，剩下（包括其余的 0 到 x - 1 和比 x 大的）都是可删可不删的。

显然，我们能决定是否删去的只有可删可不删的。

而可删可不删的数字数量是固定的。所以删一个、删两个、删三个……直到删完都是符合题意的。

这样，我们删除数字的总数就是必删的数量加上我们选择的可删可不删的数量。后者是连续的，前者是不变的。总数必然也是连续的。

证明结束。这样我们就把问题转化成了多次区间加的问题。

区间左端点是必删的数量，右端点是必删的数量加上所有可删可不删的数量，即 n 减去不可删的数量，也就是 n - \operatorname{MEX}。

用一个桶就可以知道必删的数量。\operatorname{MEX} 是我们枚举的，当然也知道。这样区间的左右端点就知道了。然后就是多次修改和一次总体查询了，差分模板即可。

最后由于删数后 \operatorname{MEX} 肯定不会增加，所以枚举的上界就是原数列的 \operatorname{MEX}。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 55;
int n, a[N], b[N], c[N];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int TTT;
    cin >> TTT;
    while (TTT--) {
        cin >> n;
        for (int i = 1;i <= n;i++) {
            cin >> a[i];
            b[a[i]]++;
        }
        int MEX = 0;
        for (int i = 0;i <= n;i++) {
            if (b[i] == 0) {
                MEX = i;
                break;
            }
        }
        for (int i = MEX;i >= 0;i--) {
            c[b[i]]++;
            c[n - i + 1]--;
        }
        for (int i = 0;i <= n;i++) {
            if (i >= 1) c[i] += c[i - 1];
            cout << c[i] << " ";
        }
        cout << "\n";
        for (int i = 0;i <= n + 1;i++)
            a[i] = b[i] = c[i] = 0;
    }
    return 0;
}