RT，回滚莫队板子

正确性应该是没问题，最后一个点TLE，其他AC，求卡常/kk

// Problem: P4137 Rmq Problem / mex
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4137
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Auther: Sugar_Pigeon
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define M 200005
int zz1,nans,fans,mex,ccnt;
int ftag[M];
int n,m,a[M],ox,oy,tag[M],ll[M],rr[M],fp[M],Ql[M],Qr[M],cntq;
int len,cntk;
struct node {
	int ql,qr,id,ans;
}q[M];
bool cmp(node x,node y) {
	return (fp[x.ql]==fp[y.ql]?x.qr<y.qr:fp[x.ql]<fp[y.ql]);
}
bool cmpid(node x,node y) {
	return x.id<y.id;
}
void Ins(int id) {
	tag[a[id]]++;
	if(a[id]==mex) {
		for(register int i=a[id];1;++i) {
			if(!tag[i]) {mex=i; break;}
		}
	}
	return;
}
void Del(int id) {
	tag[a[id]]--;
	return;
}
void Sol(int qid) {
	ccnt++;
	for(register int i=q[qid].ql;i<=q[qid].qr;++i) {
		ftag[a[i]]=ccnt;
	}
	for(register int i=0;i<=q[qid].qr-q[qid].ql+2;++i) {
		if(ftag[i]!=ccnt) {
			q[qid].ans=i;
			return;
		}
	}
	return;
}
signed main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m,len=sqrt(n),cntk=ceil(n*1.0/len);
	for(register int i=1;i<=cntk;++i) {
		ll[i]=rr[i-1]+1,rr[i]=ll[i]+len-1;
		if(rr[i]>n) rr[i]=n;
		for(register int j=ll[i];j<=rr[i];++j) {
			fp[j]=i;
		}
	}
	for(register int i=1;i<=n;++i) cin>>a[i];
	for(register int i=1;i<=m;++i) cin>>q[i].ql>>q[i].qr,q[i].id=i;
	sort(q+1,q+1+m,cmp);
	for(register int i=1;i<=m;++i) {
		if(fp[q[i].ql]>cntq) {
			Qr[cntq]=i-1;
			Ql[fp[q[i].ql]]=i;
			cntq=fp[q[i].ql];
		}
	}
	Qr[cntq]=m;
	for(register int bk=1;bk<=cntk;++bk) {
		if(!Ql[bk]) continue;
		zz1=rr[bk]-1,mex=0;
		memset(tag,0,sizeof(tag));
		for(register int i=Ql[bk];i<=Qr[bk];++i) {
			if(fp[q[i].qr]==bk) { // 左右端点在同一块
				Sol(i);
				continue;
			}
			for(register int j=zz1+1;j<=q[i].qr;++j) Ins(j); // 更新至右端点
			zz1=q[i].qr,fans=mex;
			for(register int j=rr[bk];j>=q[i].ql;--j) Ins(j); // 更新至左端点
			q[i].ans=mex,mex=fans;
			for(register int j=q[i].ql;j<=rr[bk];++j) Del(j); // 左端点回退至此块最右端
		}
	}
	for(register int i=1;i<=m;++i) ftag[q[i].id]=q[i].ans; // 废弃数组回收利用把每个询问的答案放到其应该在的位置上
	for(register int i=1;i<=m;++i) cout<<ftag[i]<<endl;
	return 0;
}