90分回滚莫队求卡常(已经尝试了讨论区所有卡常方法)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int dt[N],a[N],cnt[N],ans[N];
int n,m,len,clean[N],cl;
struct nod{
	int id,l,r;
}q[N];
inline bool cmp(nod x,nod y){
	int i=dt[x.l],j=dt[y.l];
	if(i!=j)return i<j;
	return x.r<y.r;
}
inline void add(int x,int& res){
	cnt[x]++;
	while(cnt[res])res++;
}
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline void write(int x){
    if(x<0){
    	putchar('-');
		x=-x;
	}
    if(x>9) 
		write(x/10);
    putchar(x%10+'0');
}
int main(){
	n=read();
	m=read();
	len=sqrt(n);
	for(int i=1;i<=n;++i){
		a[i]=read();
		dt[i]=(i-1)/len+1;
	}
	for(int i=1;i<=n;++i){
		q[i].l=read(),q[i].r=read();
		q[i].id=i;
	}
	sort(q+1,q+m+1,cmp);
	for(int x=1;x<=m;){
		int y=x;
		while(y<=m&&dt[q[x].l]==dt[q[y].l])y++;
		int right=(dt[q[x].l])*len;
		while(x<y&&q[x].r<=right){
			int res=0;
			for(int k=q[x].l;k<=q[x].r;k++)add(a[k],res);
			ans[q[x].id]=res;
			for(int k=q[x].l;k<=q[x].r;k++)cnt[a[k]]--;
			x++;
		}
		int res=0;
		int l=right+1,r=right;
		while(x<y){
			while(r<q[x].r){
				add(a[++r],res);
				clean[++cl]=a[r];
			}
			int mid=res;
			while(l>q[x].l)add(a[--l],res);
			ans[q[x].id]=res;	
			while(l<=right)cnt[a[l++]]--;
			res=mid;
			x++;
		}
		for(int i=1;i<=cl;i++){
			cnt[clean[i]]=0;
		}
		cl=0;
	}
	for(int i=1;i<=m;++i){
		write(ans[i]);
		putchar('\n');
	}
	return 0;
}