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

· · 题解

奶龙。

根据经典结论，极短 mex 区间 \mathcal{O} (n) 个。

用值域线段树找出所有的支配对，即每次找到 a_r 之后更新所有 \operatorname{mex}_{l,r}=a_r 的点，当前 r 和所有的区间右端点就是支配对。

好，我们现在清空线段树，找出所有支配对之后在右端点加入，然后继续用值域线段树维护即可。

可以参考 CF1148H。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=4e6+5;
const int inf=1e9+7;
#define mkp make_pair
#define vi vector<int>
namespace sgt{
#define ls (o<<1)
#define rs (ls|1)
#define mid ((l+r)>>1)
    int L[M],R[M];
    int mn[M];
    void pushup(int o){mn[o]=min(mn[ls],mn[rs]);}
    void build(int o,int l,int r){
        L[o]=l,R[o]=r;
        mn[o]=0;if(l==r)return;
        build(ls,l,mid),build(rs,mid+1,r);
    }
    void mdf(int o,int pos,int x){
        int l=L[o],r=R[o];
        if(l==r){mn[o]=x;return;}
        mdf((pos<=mid?ls:rs),pos,x);
        pushup(o);
    }
    int qrymn(int o,int lt,int rt){
        if(lt>rt)return inf;
        int l=L[o],r=R[o];
        if(l>=lt&&r<=rt)return mn[o];
        int res=inf;
        if(lt<=mid)res=min(res,qrymn(ls,lt,rt));
        if(rt>mid)res=min(res,qrymn(rs,lt,rt));
        return res;
    }
    int getmex(int p){//找到第一个位置使得最后出现的位置 <p
        int o=1,res=inf;
        while(1){
            if(L[o]==R[o]){res=L[o];break;}
            o=mn[ls]<p?ls:rs;
        }
        return res;
    }
#undef ls
#undef rs
#undef mid
}
int n,q;
struct Qry{
    int l,id;
};vector<Qry>qrs[N];
int Ans[N];
int a[N];
vector<pair<int,int>>rgs[N];
int mps[N];
void init(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]),a[i]=min(a[i]-1,n+1);
    sgt::build(1,0,n+1);
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        qrs[r].emplace_back((Qry){l,i});
    }
    for(int i=1;i<=n;i++){
        int L=mps[a[i]]+1,R=min(i,sgt::qrymn(1,0,a[i]-1));
        mps[a[i]]=i,sgt::mdf(1,a[i],i);
        if(a[i])rgs[i].emplace_back(mkp(i,0));
        int r=R,l=0;
        while(r>=L){
            int mex=sgt::getmex(r);
            rgs[i].emplace_back(mkp(r,mex));
            l=max(L,mps[mex]+1);r=l-1;
        }
    }
}

void work(){
    for(int i=0;i<=n;i++)mps[i]=0;
    sgt::build(1,0,n+1);
    for(int i=1;i<=n;i++){
        for(auto [LL,val]:rgs[i]){
            int L=mps[val]+1;
            int R=min(LL,sgt::qrymn(1,0,val-1));
            mps[val]=LL,sgt::mdf(1,val,LL);
            //int r=R,l=0;
            //while(r>=L){
            //  int mex=sgt::getmex(r);
            //  rgs[i].emplace_back(mkp(r,mex));
            //  l=max(L,mps[mex]+1);r=l-1;
            //}
        }
        for(auto [l,id]:qrs[i])
            Ans[id]=sgt::getmex(l);
    }
    for(int id=1;id<=q;id++)
        printf("%d\n",Ans[id]+1);
}
int main(){
    init();
    work();
    return 0;
}