题解：CF1870G MEXanization

· · 题解

首先容易发现，除了第一个数以外，后面的 n-1 个前缀的答案都是单调不降的，证明这是显然的。

于是我们考虑去 check 每个数是否能成为答案。

对于一个数 x，我们考虑这样去 check：

我们设 cnt_i 表示 i 在前缀中出现的次数，那么我们只用满足 \forall i\in[0,x-1]，都有 cnt_i\ge1。

于是我们直接从大到小扫 i，如果当前的 cnt_i\le0，那么就用 j\in [0,i-1] 的 cnt_j 凑出 1-cnt_i 个 i 即可。

这样直接模拟单次 check 能做到 O(n)，总共就是 O(n^2) 的了。

考虑优化，先把上述的贪心换种形式：

我们设 p 表示当前的 cnt_i 要分多少个给 i 后面的，s 表示后面的有多少是多余的。

于是我们对于每一个 i，有 s 加上 \max(0,cnt_i-p-1)，p 加上 \max(0,1-(cnt_i-p))。

其实容易发现，我们 p 的有效加操作是只有 \sqrt n 次的。

考虑证明，由于 \sum cnt 是 O(n) 量级的，而我们 p 减的总数应该是 \frac{p\times(p+1)}{2}，所以 p 自然是 O(\sqrt n) 量级的。

于是我们直接用线段树二分去找 p 的有效操作，这样就是 O(n\sqrt n\log n) 的。

接着考虑优化，由于直接找是真的没什么前途，所以我们考虑直接 dfs 线段树。

设 mn_x 表示区间 cnt_i 的最小值，sum_x 表示区间 cnt_i 的和。

还是考虑我们刚刚的做法，在线段树上，我们依旧从后往前，但是时间复杂度是不变的。

考虑剪枝一下，也就是对于线段树上节点 (x,l,r)：如果 mn_x-1\ge p，那么 s 加上 sum_x-(r-l+1)(p+1)，然后返回。

发现这样写了后就可以通过了。

考虑分析一下时间复杂度：我们一层一层考虑，对于所有大小为 2^k 的区间从左到右第 x 个节点，若它的子树中有至少一个可以贡献的 p，那么 \sum cnt_j 会至少减少 x2^k，所以不同的 x 最多 \sqrt{\dfrac{n}{2^k}} 种。对每一层求和后明显发现总量是 O(\sqrt n) 量级的。

总时间复杂度为 \mathcal{O}(n\sqrt{n})。

#include<bits/stdc++.h>
#define ll long long
#define pc putchar
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
int pstk[40];
inline void write(int x){
    if(!x)return putchar('0'),void();
    if(x<0)putchar('-'),x=-x;
    int len=0;for(;x;x/=10)pstk[++len]=x%10;
    while(len)putchar(pstk[len--]+'0');
}
const int Maxn=2e5+5;
int n,a[Maxn];
struct Tree{int data,mn;}t[Maxn<<2];
int V[Maxn];
void build(int x,int l,int r){
    if(l==r)return void(t[x]={0,0});
    int mid=l+r>>1;
    build(x<<1,l,mid);build(x<<1|1,mid+1,r);
}
void change(int x,int l,int r,int d,int p){
    if(l==r){t[x].data+=p;t[x].mn+=p;return;}
    int mid=l+r>>1;
    if(mid>=d)change(x<<1,l,mid,d,p);
    else change(x<<1|1,mid+1,r,d,p);
    t[x].mn=min(t[x<<1].mn,t[x<<1|1].mn);
    t[x].data=t[x<<1].data+t[x<<1|1].data;
}
int cnt[Maxn];
int ok;
void dfs(int x,int l,int r,int R,ll&d,ll&z){
    if(ok)return;
    if(t[x].mn-1>=d&&r<=R){
        z+=1ll*t[x].data-1ll*(d+1)*(r-l+1);
        return;
    }
    if(l==r){d+=1ll-1ll*(t[x].data-d);if(d>n)ok=1;return;}
    int mid=l+r>>1;
    if(mid<R)dfs(x<<1|1,mid+1,r,R,d,z);dfs(x<<1,l,mid,R,d,z);
}
inline bool check(int x){
    ll d=0,z=0;
    ok=0;if(x>1)dfs(1,1,n,x-1,d,z);
    if(z+cnt[0]-d>=1){
        cnt[0]-=V[x];cnt[x]=V[x];
        change(1,1,n,x,V[x]);
        return true;
    }
    return false;
}
inline void solve(){
    n=read();
    int ans=1;build(1,1,n);
    for(int i=0;i<=n+1;i++)V[i]=cnt[i]=0;
    for(int i=1;i<=n;i++){
        a[i]=read();
        V[a[i]]++;
        if(a[i]>=ans||!a[i])cnt[0]++;
        else change(1,1,n,a[i],1),cnt[a[i]]++;
        if(i==1)write(max(1,a[i])),pc(' ');
        else{
            while(check(ans))ans++;
            write(ans-1);pc(' ');
        }
    }
    pc('\n');
}
int main(){
    int T=read();
    while(T--)solve();
    return 0;
}
/*
20
18 12 18 6 4 14 11 5 8 8 6 11 11 6 18 2 1 6 13 11 

1
6
4 3 0 0 0 0
*/