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
",q[i].ans);
}