P9970 题解

· · 题解

推销博客！第 10 篇。

前置知识：P4137 的在线单次 O(\log n) 求区间 \text{mex} 做法，CF1870E 的结论。

赛事做繁了，没冲出来。发现第二篇题解难理解，第一篇题解有个细节繁了，于是我结合了一下。除去主席树板子，代码非常短。

这篇题解是目前第一篇题解和第二篇的结合，由重合请见谅。

如果不想看结论证明直接忽略即可，没啥影响。

称 [l,r] 是极小区间，当且仅当不存在 [L,R]\varsubsetneq[l,r]，\text{mex}(l,r)=\text{mex}(L,R)。则有结论：极小区间只有 O(n) 个。

考虑如何求所有极小区间。如果直接按证明方法求是非常难写的。于是考虑巧妙方法。

设 \text{mex}(l,r)=x，则称 [l,r] 为 \text{mex}_x 区间。

考虑一个 \text{mex}_x 的极小区间，同样不妨设 a_l>a_r，则由于极小性，于是 a_r 在 (l,r) 中没有出现。

考虑删去 a_l 之后，\text{mex} 变为 a_l，不妨设 \text{mex}_{a_l} 区间 [l+1,r] 对应的极小子区间为 [L,R]，则 a_r 一定在 [L,R] 中出现，于是 R=r。

考虑从 x=0\to n+1 依次求出所有 \text{mex}_x 极小区间。对于每个 x 维护 \text{mex}_x 极小区间的 vector。

每次先把所有 \text{mex}_{x-1} 区间进行如上扩展，设一个扩展完后 \text{mex}=y，则把新区间丢到 y 的 vector 里。这里求扩展完的 \text{mex} 用上面说的单次 O(\log n) 的方法。

这时候所有 \text{mex}_x 极小区间都在 x 的 vector 里了，但注意扩展完的不一定都是极小的，于是排除掉即可。就不多不少的求出了 \text{mex}_x 极小区间，一直做下去即可。记得初始化极小 \text{mex}_{0/1} 区间。

由于极小区间总共只有 O(n) 个，乘上求区间 \text{mex} 的 \log，于是复杂度为 O(n\log n)。

求出所有极小区间后，考虑所有对应 \text{mex}_x 的极小子区间 [l,r] 的大区间的形态。

设 l 左侧第一个 x 的位置为 L-1，r 右侧第一个 x 的位置为 R+1。

则所有对应的大区间为：左端点在 [L,l]，右端点在 [r,R] 的所有区间。于是 \forall len\in [r-l+1,R-L+1]，存在长为 len 的区间 \text{mex}=x。

于是问题就转化成了：维护 n 个集合，区间插入一个数，最终对所有集合求 \text{mex}。把插入操作差分，用一个 set 动态维护 \text{mex} 即可。具体看代码。

代码：

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define fi first
#define se second
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1e5+5;
int n,V,a[N],cnt[N],tot,rt[N];
vector<int>g[N],ad[N],dl[N];vector<P>h[N];
namespace MEX
{
    struct node{int ls,rs,x;}b[N*25];
    void build(int l,int r,int &wz)
    {
        b[wz=++tot]={0,0,0};if(l==r) return;
        int mid=(l+r)>>1;build(l,mid,b[wz].ls);build(mid+1,r,b[wz].rs);
    }
    void updata(int l,int r,int &wz,int wz1,int x,int y)
    {
        b[wz=++tot]=b[wz1];if(l==r) return b[wz].x=y,void();
        int mid=(l+r)>>1;
        if(x<=mid) updata(l,mid,b[wz].ls,b[wz1].ls,x,y);
        else updata(mid+1,r,b[wz].rs,b[wz1].rs,x,y);
        b[wz].x=min(b[b[wz].ls].x,b[b[wz].rs].x);
    }
    int query(int l,int r,int wz,int x)
    {
        if(l==r) return l;int mid=(l+r)>>1;
        if(b[b[wz].ls].x<x) return query(l,mid,b[wz].ls,x);
        return query(mid+1,r,b[wz].rs,x);
    }
    inline int que(int l,int r){return query(0,V,rt[r],l);}
}using MEX::que;
int vis[1005][1005];
inline void add(int l,int r,int L,int R,int x){ad[L-r+1].push_back(x);dl[R-l+2].push_back(x);}
inline void getans()
{
    set<int>S;for(int i=0;i<=n;i++) cnt[i]=0,S.insert(i);
    for(int i=1;i<=n;i++)
    {
        for(int j:ad[i]) if(!cnt[j]++) S.erase(j);
        for(int j:dl[i]) if(!--cnt[j]) S.insert(j);cout<<*S.begin()<<" ";
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
    V=n+3;for(int i=0;i<=V;i++) g[i].push_back(0);
    for(int i=1;i<=n;i++) cin>>a[i],g[a[i]].push_back(i);
    MEX::build(1,V,rt[0]);for(int i=1;i<=n;i++) MEX::updata(0,V,rt[i],rt[i-1],a[i],i);
    for(int i=0;i<=V;i++) g[i].push_back(n+1);
    for(int i=1;i<=n;i++) a[i]?h[0].push_back({i,i}):h[1].push_back({i,i});
    for(int i=1;i<=V;i++)
    {
        for(auto [l,r]:h[i-1])
        {
            #define all g[i-1].begin(),g[i-1].end()
            int L=*(--lower_bound(all,l)),R=*upper_bound(all,r);
            if(L) h[que(L,r)].push_back({L,r});
            if(R<=n) h[que(l,R)].push_back({l,R});
        }sort(h[i].begin(),h[i].end(),[](P x,P y){return x.fi==y.fi?x.se<y.se:x.fi>y.fi;});
        vector<P>G;int las=2e9;
        for(auto [l,r]:h[i]) if(las>r) G.push_back({l,r}),las=r;swap(G,h[i]);
    }
    for(int i=0;i<=V;i++)
        for(auto [l,r]:h[i])
            #define all g[i].begin(),g[i].end()
            add(*(--lower_bound(all,l))+1,l,r,*upper_bound(all,r)-1,i);
    return getans(),0;
}