题解：CF2146E Yet Another MEX Problem

xzy090626 · 2025-09-27 13:04:48 · 题解

• 我们考虑对于每个右端点 i，选择枚举 [l,i] 的区间 \text{MEX}=x。

• 注意到直接枚举 x 是不容易做的，因为我们没办法钦定 [0,x) 全部出现；但是只要 x 没有出现，就一定有 \text{MEX}\leq x，而此时 x 的贡献不优，因此这么做不会算大贡献。

• 现在考虑如何维护每个 x 的贡献。设 x 上一次出现的位置为 p（特别地，没有出现则为 0），那么由于 x 不能出现，所以有 l>p。此时显然令 l=p+1 最优，贡献就是 \sum\limits_{k=p+1}^i [a_k>x]。

• 发现这个贡献形式非常平凡，每次加入 a_i 的时候对于 x<a_i 的 x 贡献加一即可。另外加入的时候还要注意特殊更新 x=a_i 的情况，将它的贡献置为 0。

• 现在需要支持的操作是区间加，单点赋值和全局查询。显然可以线段树维护之，复杂度 O(n\log n)。

好久没写线段树了。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 7;
int n,m;
int tr[N*4],tag[N*4];
void pushdown(int x){
    tag[x*2] += tag[x];
    tag[x*2+1] += tag[x];
    tr[x*2] += tag[x];
    tr[x*2+1] += tag[x];
    tag[x] = 0;
}
void build(int x,int l,int r){
    tr[x] = tag[x] = 0;
    if(l==r){
        return;
    }
    int mid = (l+r)/2;
    build(x*2,l,mid);
    build(x*2+1,mid+1,r);
    tr[x] = max(tr[x*2],tr[x*2+1]);
}
void update(int x,int l,int r,int L,int R){
    if(L>r || l>R) return;
    if(l<=L && R<=r){
        tr[x] += 1;
        tag[x] += 1;
        return;
    }
    pushdown(x);
    int mid = (L+R)/2;
    update(x*2,l,r,L,mid);
    update(x*2+1,l,r,mid+1,R);
    tr[x] = max(tr[x*2],tr[x*2+1]);
}
void mdf(int x,int l,int r,int pos){
    if(l==r){
        tr[x] = 0;
        return;
    }
    pushdown(x);
    int mid = (l+r)/2;
    if(pos<=mid) mdf(x*2,l,mid,pos);
    else mdf(x*2+1,mid+1,r,pos);
    tr[x] = max(tr[x*2],tr[x*2+1]);
}
void solve(){
    cin>>n;
    build(1,0,n);
    for(int i=1;i<=n;++i){
        int x;cin>>x;
        update(1,0,x-1,0,n);
        mdf(1,0,n,x);
        cout<<tr[1]<<' ';
    }
    cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;cin>>T;
    for(int _=1;_<=T;++_){
        solve();
    }
    return 0;
}