P4137 Rmq Problem / mex

Luogu4137

静态求一个区间中没有出现过的最小的自然数

删除很简单 , 但添加很麻烦 , 直接用莫队会被卡 , 可以一开始处理出所有的答案 , 然后就只管删除就行了 , 即回滚莫队

怒抄题解

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){
    register LL x=0,f=1;register char c=getchar();
    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();
    return f*x;
}

const int N=3e5+5;

int a[N],b[N],bel[N],cnt[N],t[N];
int n,m,Ans,Bsize,l,r,resR;

struct Query{
    int l,r,id,ans;
    inline friend bool operator< (Query a,Query b){
        if(bel[a.l]!=bel[b.l]) return a.l<b.l;
        return a.r>b.r;
    }
}q[N];
inline bool cmp(Query a,Query b){return a.id<b.id;}

inline void add(int x){
    if(x>n+1) return;
    cnt[x]++;
}
inline void del(int x,int &ans){
    if(x>n+1) return;
    if(--cnt[x]==0) ans=min(ans,x);
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) b[i]=a[i]=read();
    for(int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;

    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++) if(b[i]==Ans) Ans++;

    Bsize=sqrt(n);
    for(int i=1;i<=n;i++) bel[i]=bel[i-1]+(i%Bsize==1);
    sort(q+1,q+m+1);
    for(int i=1;i<=n;i++) add(a[i]);//先把答案全部加上,回滚莫队只管删除
    l=1,r=n,resR=Ans;
    for(int i=1;i<=m;i++){
        if(bel[q[i].l]==bel[q[i].r]){
            for(int j=q[i].l;j<=q[i].r;j++) if(a[j]<=n+1) t[a[j]]++;
            q[i].ans=0;
            while(t[q[i].ans]) q[i].ans++;
            for(int j=q[i].l;j<=q[i].r;j++) if(a[j]<=n+1) t[a[j]]--;
            continue;
        }
        while(bel[l]<bel[q[i].l]){
            while(r<n) add(a[++r]);
            del(a[l++],Ans);
            resR=Ans;
        }
        resR=Ans;
        while(r>q[i].r)
            del(a[r--],resR);
        int res=resR,_l=l;
        while(_l<q[i].l) del(a[_l++],res);
        q[i].ans=res;
        while(_l>l) add(a[--_l]);
    }
    sort(q+1,q+m+1,cmp);
    for(int i=1;i<=m;i++)
        printf("%d\n",q[i].ans);
}

P4137 Rmq Problem / mex

原文：https://www.cnblogs.com/lizehon/p/10643221.html