题解：P13780 「o.OI R2」愿天堂没有分块

· · 题解

VP 的时候没做出来，回头一看连区间 \operatorname{mex} 都不会，回头补了一手。

前置知识：主席树求区间 \operatorname{mex}。

此处为板题传送门。

我们定义某 \operatorname{mex}=x 的极小 \operatorname{mex} 区间为 [L,R]，则对于其任意一个子区间（不包含自身），\operatorname{mex}<x。

这样的区间的数量是 O(N) 的，有一个上限是 N\times2。

所以我们可以预处理出所有的极小 \operatorname{mex} 区间。

具体是：先处理出 \operatorname{mex}\leq 2 的区间，然后从 2 开始扩展，找到其前后第一个等于 \operatorname{mex} 的数，计算扩展后的区间的 \operatorname{mex}。最后求极小，对于 \operatorname{mex} 值相同的备选区间，排序然后扫一遍即可。

然后对于每一个询问 [L,R]，我们需要求最小的 x，使得 [L,R] 内部没有 \operatorname{mex}=x 的极小区间，可以用权值线段树二分以及扫描线解决。

具体的：我们把所有极小 \operatorname{mex} 区间挂到其 L 上，从大到小对 L 扫描线，权值线段树维护最小的 R 的最大值，对于询问线段树二分即可。

代码如下。

#include<bits/stdc++.h>
using namespace std;
#define PII pair<int,int>
#define fir first
#define sec second
const int N=1e6+5;
const int NUM=1e6+1;
int n,m,a[N],ans[N];
bool cmp(PII a,PII b){
    if(a.fir==b.fir)return a.sec<b.sec;
    return a.fir>b.fir;
}
vector<int> G[N];
vector<PII> P[N],V[N],Q[N];
namespace segp{
    int v[N<<5],ls[N<<5],rs[N<<5],rt[N],cnt;
    void init(){rt[0]=cnt=0;}
    int update(int pre,int x,int y,int l,int r){
        int p=++cnt;
        ls[p]=ls[pre],rs[p]=rs[pre];
        if(l==r){v[p]=y;return p;}
        int mid=l+r>>1;
        if(x<=mid)ls[p]=update(ls[pre],x,y,l,mid);
        else rs[p]=update(rs[pre],x,y,mid+1,r);
        v[p]=min(v[ls[p]],v[rs[p]]);return p;
    }
    int query(int p,int L,int l,int r){
        if(l==r)return l;
        int mid=l+r>>1;
        if(v[ls[p]]<L)return query(ls[p],L,l,mid);
        else return query(rs[p],L,mid+1,r);
    }
}
namespace seg{
    int v[N<<5],ls[N<<5],rs[N<<5],rt,cnt;
    void init(){rt=cnt=0;v[0]=NUM+1;}
    void update(int &p,int x,int y,int l,int r){
        if(!p){p=++cnt;ls[p]=rs[p]=0;v[p]=NUM+1;}
        if(l==r){v[p]=min(v[p],y);return ;}
        int mid=l+r>>1;
        if(x<=mid)update(ls[p],x,y,l,mid);
        else update(rs[p],x,y,mid+1,r);
        v[p]=max(v[ls[p]],v[rs[p]]);
    }
    int query(int p,int R,int l,int r){
        if(l==r)return l;
        int mid=l+r>>1;
        if(v[ls[p]]>R)return query(ls[p],R,l,mid);
        else return query(rs[p],R,mid+1,r);
    }
}
bool check(int l,int r,int x){
    if(segp::query(segp::rt[r],l,1,NUM)==x)return 1;
    else return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    segp::init(),seg::init();
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],G[a[i]].push_back(i);
    for(int i=1;i<=n;i++)P[(a[i]==1)+1].push_back({i,i});
    for(int i=1;i<=n;i++)
        segp::rt[i]=segp::update(segp::rt[i-1],a[i],i,1,NUM);
    for(int i=2;i<=n;i++){
        for(auto p:P[i]){
            int L=p.fir,R=p.sec;
            auto nxt=lower_bound(G[i].begin(),G[i].end(),R+1);
            auto pre=lower_bound(G[i].begin(),G[i].end(),L);
            if(nxt!=G[i].end())P[segp::query(segp::rt[*nxt],L,1,NUM)].push_back({L,*nxt});
            if(pre!=G[i].begin())--pre,P[segp::query(segp::rt[R],*pre,1,NUM)].push_back({*pre,R});
        }
        sort(P[i+1].begin(),P[i+1].end(),cmp);
        vector<PII> t;int pre=NUM;
        for(auto p:P[i+1]){
            if(p.sec<pre)t.push_back(p);
            pre=min(pre,p.sec);
        }
        P[i+1]=t;
    }
    for(int i=1;i<=n+1;i++)
        for(auto p:P[i])
            V[p.fir].push_back({p.sec,i});
    int x,y;
    for(int i=1;i<=m;i++){
        cin>>x>>y;
        Q[x].push_back({y,i});
    }
    for(int l=n;l>=1;l--){
        for(auto p:V[l])
            seg::update(seg::rt,p.sec,p.fir,1,NUM);
        for(auto p:Q[l])
            ans[p.sec]=seg::query(seg::rt,p.fir,1,NUM);
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
}