可持久化线段树、树状数组、莫队、值域分块

长度为 $n$ 的序列的 $\operatorname{mex}$ 值至多为 $n$，因此问题值域同为 $O(n)$。

Solution 1：值域树状数组能够在 $O(\log n)$ 时间复杂度内倍增出其维护序列的 $\operatorname{mex}$ 值。

维护桶 $w$ 和树状数组 $c$，以 $w_i$ 表示当前 $i$ 的出现次数，以 $c_i$ 表示当前 $i$ 是否出现。

莫队配合树状数组，由于 $n,m$ 同阶，时间复杂度 $O(n \sqrt{n} \log n)$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=450;
struct Query{int i,l,r;};
int n,m,l,r,a[200'005],c[200'005],w[200'005],ans[200'005];
inline void add(int x,int y){
    ++x;//0-index to 1-index
    while(x<=n) c[x]+=y,x+=x&-x;
}
inline int mex(){
    static const int lim=__lg(n);
    int ret=0;
    for(int i=1<<lim;i;i>>=1) if(ret+i<=n&&c[ret+i]==i) ret+=i;
    return ret;
}
inline void update(int x,int T){
    if(T==1){
        ++w[x];
        if(x<n&&w[x]==1) add(x,1);
    }
    else{
        --w[x];
        if(x<n&&w[x]==0) add(x,-1);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    vector<Query> v(m);
    for(auto &[i,l,r]:v){
        static int cnt;
        cin>>l>>r,i=++cnt;
    }
    sort(v.begin(),v.end(),[](auto x,auto y){
        if(x.l/B!=y.l/B) return x.l<y.l;
        return (x.l/B)&1 ? x.r>y.r:x.r<y.r;
    });
    l=1,r=0;
    for(auto [i,ql,qr]:v){
        while(l>ql) update(a[--l],1);
        while(r<qr) update(a[++r],1);
        while(l<ql) update(a[l++],-1);
        while(r>qr) update(a[r--],-1);
        ans[i]=mex();
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

Solution 2：值域分块能够实现 $O(1)$ 修改，$O(\sqrt{V})$ 查询 $\operatorname{mex}$ 的功能。

本题中由于 $\operatorname{mex}$ 的良好性质，值域范围与 $n$ 同阶，故查询的时间复杂度为 $O(\sqrt{n})$。

经过测试块长取 $800$ 左右时程序效率最高。

时间复杂度 $O(n \sqrt{n})$。

#include<bits/stdc++.h>
using namespace std;
constexpr int B=800;
struct Query{int i,l,r;};
int n,m,a[200'005],w[200'005],ans[200'005],br[200'005/B+5],res[200'005/B+5];
inline void add(int x){if(x<n&&(++w[x])==1) --res[x/B];}
inline void del(int x){if(x<n&&(--w[x])==0) ++res[x/B];}
inline int mex(){
    int ret=0;
    while(res[ret/B]==0) ret=br[ret/B]+1;
    while(w[ret]!=0) ++ret;
    return ret;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=0;i<=n;i++) ++res[i/B],br[i/B]=i;//值域 [0,n] 范围 只处理小于 n 的数来保证最后一个块不满
    vector<Query> v(m);
    for(auto &[i,l,r]:v){
        static int cnt;
        cin>>l>>r,i=++cnt;
    }
    sort(v.begin(),v.end(),[](auto x,auto y){
        if(x.l/B!=y.l/B) return x.l<y.l;
        return (x.l/B)&1 ? x.r>y.r:x.r<y.r;
    });
    for(auto [i,ql,qr]:v){
        static int l=1,r=0;
        while(l>ql) add(a[--l]);
        while(r<qr) add(a[++r]);
        while(l<ql) del(a[l++]);
        while(r>qr) del(a[r--]);
        ans[i]=mex();
    }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}

Solution 3：首先考虑静态问题，然后用数据结构快速维护静态问题端点移动造成的影响。

给定左端点 $l$ 求区间 $[l,r]$ 的 $\operatorname{mex}$，对每个值 $x$ 维护 $x$ 在区间 $[1,r]$ 中最后一次出现的位置 $p_x$ 即可二分答案，如果对于所有小于 $mid$ 的值 $k$ 都有 $p_k \geq l$ 则说明 $mid$ 合法。

线段树维护 $p_x$ 可以做到 $O(\log n)$ 回答单个询问。

将当前右端点从 $r$ 移动到 $r+1$ 只需要修改 $p_{a_{r+1}}$ 的值，可以在 $O(\log n)$ 时间复杂度内完成，离线询问即可，但我不喜欢离线数据结构。

可持久化线段树维护 $n$ 棵线段树，第 $i$ 棵线段树的右端点为 $i$，对于询问给定的 $l,r$ 直接在第 $r$ 棵线段树上二分答案。

总体时间复杂度 $O(n \log n)$，空间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int w,ls,rs;}s[200'005*20];
int n,m,seg,ro[200'005];
void update(int &u,int las,int l,int r,int p,int k){
    if(u==0) u=++seg;
    if(l==r) return s[u].w=k,void();
    int mid=(l+r)>>1;
    if(p<=mid){
        s[u].ls=++seg,s[u].rs=s[las].rs;
        s[seg]=s[s[las].ls];
        update(s[u].ls,s[las].ls,l,mid,p,k);
    }
    else{
        s[u].rs=++seg,s[u].ls=s[las].ls;
        s[seg]=s[s[las].rs];
        update(s[u].rs,s[las].rs,mid+1,r,p,k);
    }
    s[u].w=min(s[s[u].ls].w,s[s[u].rs].w);
}
int query(int u,int l,int r,int p){//找第一个不符合条件的位置
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(s[s[u].ls].w>=p) return query(s[u].rs,mid+1,r,p);
    return query(s[u].ls,l,mid,p);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){//权值+1处理
        static int x;
        scanf("%d",&x);
        if(x<=n) update(ro[i],ro[i-1],1,n+5,x+1,i);
        else ro[i]=ro[i-1];
    }
    for(int i=1;i<=m;i++){
        static int l,r,ans;
        scanf("%d%d",&l,&r);
        ans=query(ro[r],1,n+5,l)-1;
        printf("%d\n",ans);
    }
    return 0;
}