Solution P13780 「o.OI R2」愿天堂没有分块

· · 题解

vp 了一下这题，结果拼尽全力无法战胜 mex。

考虑找出哪些极小的区间（记为关键区间）的 mex 为 x。则只要询问区间包含了其中一个则代表询问的答案一定不为 x。

如果直接对于每个 x 找出所有的关键区间就太多了。考虑去掉某些关键区间。找出 x 在序列中出现的所有位置 0=d_1<d_2<d_3\cdots<d_{k-1}<d_k=n+1（为方便我们钦定 0,n+1 也是 x 出现的位置），显然关键区间不能跨过这些位置。

对于一个询问区间和 x，其会被 d 切成若干段，或是被完整的包含在一个 (d_j,d_{j+1}) 内。发现这样分析有许多好处：

这样感觉下来复杂度很对了，接下来是一些精细实现以满足 O(n\log n) 的时间复杂度。

首先是如何找出所有 x 对应的关键区间。发现区间内一定要有 1 到 x-1 的所有数。考虑从右往左扫描线（扫到 i），线段树维护每个值 v 在 [i,n] 内第一次出现的位置 p_v。则只需查询 t=\max_{v<a_i}p_v，那么区间 [i+1,p] 就是 a_i 对应的关键区间。同样还需要从左向右做一遍类似的扫描线。

接下来考虑如何处理询问。假设区间为 [l,r]，首先按 l 扫描线，则根据 x 对应的关键区间可知当 r\le p_{x,l} 时 x 不会出现在任何子区间的 mex 中，可以被计入答案。记关键区间集合 S_x，则 p_{x,l}=\min_{[L,R]\in S_x,L\ge l}R-1，发现其是单调的因此我们无需撤销操作（新的修改一定更优秀）。

现在问题变为：扫描线时对每个下标维护一个集合。每次修改形如给一个前缀的所有集合内加入 x。每次查询某个位置的集合内部的最小值和次小值（维护次小值是因为最小值可能等于整个询问区间的 mex，这种情况是独立的）。

修改一下问题形式：单点修改，每次查询某个后缀的最小值和次小值。这样就能用线段树单 log 维护了。

还有一个小问题：如何求某个区间的 mex？直接在上述扫描线的基础上再用线段树维护每个点第一次出现的位置即可。

时间复杂度 O(n\log n)。

// Code by UniGravity
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define forto(i,a,b) for(int i=(a),_##i(b);i<=_##i;i++)
#define forbk(i,a,b) for(int i=(a),_##i(b);i>=_##i;i--)
#define forv(i,a) for(int i(0),_##i(a);i<_##i;i++)
#define fst first
#define snd second
#define il inline
#define eb emplace_back
#define mkp make_pair
using namespace std;
il int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||'9'<c)c=='-'?(f=-1):0,c=getchar();
    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N=1000005,INF=0x3f3f3f3f;
int n,q,a[N],mxa;

struct SegTree1{
    int mx[N*4];
    il int qry(int x,int l,int r,int bg,int ed){
        if(bg<=l&&r<=ed)return mx[x];int mid=(l+r)>>1,a=-INF;
        if(bg<=mid)a=qry(x<<1,l,mid,bg,ed);if(mid<ed)a=max(a,qry(x<<1|1,mid+1,r,bg,ed));
        return a;
    }
    il void upd(int x,int l,int r,int p,int v){
        if(l==r)return mx[x]=v,void();int mid=(l+r)>>1;
        p<=mid?upd(x<<1,l,mid,p,v):upd(x<<1|1,mid+1,r,p,v),mx[x]=max(mx[x<<1],mx[x<<1|1]);
    }
    il int find(int x,int l,int r,int v){
        if(l==r)return l;int mid=(l+r)>>1;
        return mx[x<<1]>v?find(x<<1,l,mid,v):find(x<<1|1,mid+1,r,v);
    }
    il int mex(int r){
        return mx[1]<=r?(n+1):find(1,1,n,r);
    }
}mx;
int lstp[N];
vector<pii>vec[N];
il void work(bool rev){
    memset(mx.mx,INF,sizeof(mx.mx));
    forto(i,1,n+1)lstp[i]=n+1;
    forbk(i,n,1){
        int p=a[i]==1?(i+1):mx.qry(1,1,n,1,a[i]-1);
        if(p<lstp[a[i]]){
            int l=i+1,r=p;
            if(rev)swap(l,r),l=n-l+1,r=n-r+1;
            vec[a[i]].eb(l,r);
        }
        lstp[a[i]]=i,mx.upd(1,1,n,a[i],i);
    }
    forto(i,1,n+1){
        int p=i==1?1:mx.qry(1,1,n,1,i-1);
        if(p<lstp[i]){
            int l=1,r=p;
            if(rev)swap(l,r),l=n-l+1,r=n-r+1;
            vec[i].eb(l,r);
        }
    }
}

struct SegTree2{
    pii mn[N*4];
    il void build(int x,int l,int r){
        mn[x]=mkp(mxa+2,mxa+2);
        if(l==r)return;int mid=(l+r)>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
    }
    il pii pup(pii x,pii y){
        pii a;
        a.first=min(x.first,y.first);
        if(x.first==y.first)a.second=min(x.second,y.second);
        else if(x.first<y.first)a.second=min(x.second,y.first);
        else a.second=min(x.first,y.second);
        return a;
    }
    il pii ask(int x,int l,int r,int bg,int ed){
        if(bg<=l&&r<=ed)return mn[x];int mid=(l+r)>>1;
        if(bg<=mid&&mid<ed)return pup(ask(x<<1,l,mid,bg,ed),ask(x<<1|1,mid+1,r,bg,ed));
        else return bg<=mid?ask(x<<1,l,mid,bg,ed):ask(x<<1|1,mid+1,r,bg,ed);
    }
    il void upd(int x,int l,int r,int p,int v){
        if(p<l||p>r)return;
        if(l==r){
            if(v<mn[x].first)mn[x].second=mn[x].first,mn[x].first=v;
            else if(v>mn[x].second)mn[x].second=v;
            return;
        }
        int mid=(l+r)>>1;p<=mid?upd(x<<1,l,mid,p,v):upd(x<<1|1,mid+1,r,p,v);mn[x]=pup(mn[x<<1],mn[x<<1|1]);
    }
}ds;
int lst[N];
vector<pii>qry[N],upd[N];
int ans[N];

signed main(){
    n=read(),q=read();
    forto(i,1,n)a[i]=read(),mxa=max(mxa,a[i]);
    forto(i,1,q){int l=read(),r=read();qry[l].eb(r,i);}
    work(0),reverse(a+1,a+n+1),work(1),reverse(a+1,a+n+1);
    // forto(i,1,n+1){
    //     cerr<<i<<": ";
    //     for(auto[x,y]:vec[i])cerr<<'('<<x<<','<<y<<") ";
    //     cerr<<'\n';
    // }
    ds.build(1,1,n);
    forto(i,1,n+1){
        if(vec[i].size()){
            sort(vec[i].begin(),vec[i].end());
            ds.upd(1,1,n,vec[i][0].second-1,i);
            forv(j,vec[i].size()-1){
                upd[vec[i][j].first].eb(vec[i][j+1].second-1,i);
            }
            upd[vec[i].back().first].eb(n,i);
        }else{
            ds.upd(1,1,n,n,i);
        }
    }
    memset(lstp,INF,sizeof(lstp));
    forbk(i,n,1)lst[i]=lstp[a[i]],lstp[a[i]]=i;
    memset(mx.mx,INF,sizeof(mx.mx));
    forto(i,1,n)mx.upd(1,1,n,i,lstp[i]);
    forto(i,1,n){
        for(auto[j,idx]:qry[i]){
            int mex=mx.mex(j);pii res=ds.ask(1,1,n,j,n);
            ans[idx]=mex==res.first?res.second:res.first;
        }
        mx.upd(1,1,n,a[i],lst[i]);
        for(auto[j,col]:upd[i])ds.upd(1,1,n,j,col);
    }
    forto(i,1,q)printf("%d\n",ans[i]);
    return 0;
}