题解：P9970 [THUPC 2024 初赛] 套娃

· · 题解

除了一个 trick 之外都挺简单的。

首先就是这个性质：

我们设二元组 (l,r) 表示不存在 [l,r] 的子区间（不为它本身）的 mex 为 [l,r] 的 mex，那么 (l,r) 的个数是 2n 级别的。

证明可以参考 CF1870E。

于是我们可以考虑找出这些二元组。

首先 mex 为 0 和 1 的可以预处理。

然后可以发现除此之外的一个合法的二元组一定是从另一个合法二元组拓展而来的。

具体的：我们现在有一个二元组 (l,r)，设它的 mex 为 val，那么我们在 l 的左边或者 r 的右边找最近的 k，使得 a_k=val，那么区间 [k,r] 或 [l,k] 才可能成为新的满足条件的二元组。

然后我们对于每个二元组可以求出最大的区间长度使得 mex 值依旧不变，然后差分一下，扫描线扫一遍用值域线段树维护 mex 就做完了。

#include<bits/stdc++.h>
#define fir first
#define sec second
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;
}
const int Maxn=1e5+5;
int n,a[Maxn];
vector<pair<int,int> >g[Maxn];
struct Tree{
    int ls,rs,data;
}t[Maxn*50];
int root[Maxn],cnt;
void change(int&x,int y,int l,int r,int d,int p){
    x=++cnt;t[x]=t[y];if(l==r)return void(t[x].data=p);
    int mid=l+r>>1;
    if(mid>=d)change(t[x].ls,t[y].ls,l,mid,d,p);
    else change(t[x].rs,t[y].rs,mid+1,r,d,p);
    t[x].data=min(t[t[x].ls].data,t[t[x].rs].data);
}
int query(int x,int l,int r,int L){
    if(l==r)return l;
    int mid=l+r>>1;
    if(t[t[x].ls].data>=L)return query(t[x].rs,mid+1,r,L);
    return query(t[x].ls,l,mid,L);
}
inline int query(int l,int r){return query(root[r],0,n+1,l);}
vector<int>ww[Maxn];
vector<int>G[Maxn];
int cntt[Maxn];
struct seg{
    int t[Maxn<<2];
    void change(int x,int l,int r,int d,int p){
        t[x]+=p;if(l==r)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);
    }
    int query(int x,int l,int r){
        if(l==r)return l;
        int mid=l+r>>1;
        if(t[x<<1]==mid-l+1)return query(x<<1|1,mid+1,r);
        return query(x<<1,l,mid);
    }
}T;
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();while(cnt)t[cnt--]={0,0,0};
    ww[0].clear();g[0].clear();
    for(int i=1;i<=n;i++)a[i]=read(),change(root[i],root[i-1],0,n+1,a[i],i);
    g[n+1].clear();
    for(int i=1;i<=n;i++)ww[a[i]].push_back(i);
    for(int i=1;i<=n;i++){
        if(a[i]!=0)g[0].push_back(make_pair(i,i));
        if(a[i]==0)g[1].push_back(make_pair(i,i));
    }
    for(int i=0;i<=n+1;i++){
        sort(g[i].begin(),g[i].end(),[&](pair<int,int>a,pair<int,int>b){return a.fir==b.fir?a.sec<b.sec:a.fir>b.fir;});
        vector<pair<int,int> >tmp;
        int R=1e9+7;
        for(pair<int,int>j:g[i])if(j.sec<R)tmp.push_back(j),R=j.sec;
        swap(tmp,g[i]);
        for(pair<int,int>tmp:g[i]){
            int L=lower_bound(ww[i].begin(),ww[i].end(),tmp.fir)-ww[i].begin()-1;
            int R=upper_bound(ww[i].begin(),ww[i].end(),tmp.sec)-ww[i].begin();
            if(~L)g[query(ww[i][L],tmp.sec)].push_back(make_pair(ww[i][L],tmp.sec)),L=ww[i][L]+1;
            else L=1;
            if(R<ww[i].size())g[query(tmp.fir,ww[i][R])].push_back(make_pair(tmp.fir,ww[i][R])),R=ww[i][R]-1;
            else R=n;
            G[tmp.sec-tmp.fir+1].push_back(i+1);
            G[R-L+2].push_back(-i-1);
//          printf("fewfew %d %d %d\n",tmp.sec-tmp.fir+1,R-L+1,i);
        }
    }
    for(int i=1;i<=n;i++){
        for(int j:G[i]){
            if(j>0){
                j--;
                if(!cntt[j]++)T.change(1,0,n+1,j,1);
            }else{
                j=-j;
                j--;
                if(!--cntt[j])T.change(1,0,n+1,j,-1);
            }
        }
        printf("%d ",T.query(1,0,n+1));
    }
    return 0;
}