82 RE #2 #3 /kk

感觉没有地方越界 数组也开了几倍/kk

感觉也没有负数下标/kk

// wish to get better qwq

#include<bits/stdc++.h>
#define re register int
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define dec(x) fixed<<setprecision(x)

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

template<class T> inline void rd(T &x){
	int fl=1;x=0;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') fl=-fl;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	x*=fl;
}
template<class T> inline void wr(T x){
	if(x<0) x=-x,putchar('-');
	if(x<10){putchar(x+'0');return ;}
	int tmp[30]={0},cnt=0;
	while(x) tmp[cnt++]=x%10,x/=10;
	for(re i=cnt-1;i>=0;--i) putchar(tmp[i]+'0');
}

// ---------- IO ---------- //

const int N=2e5+5,SQ=450,M=2e5+5;
int n,m,len,s[N],ans[M],cnt[N];
struct question{int l,r,id,pos;}q[M];

inline int block(int x){return (x-1)/len+1;}
inline int L(int x){return (x-1)*len+1;}
inline int R(int x){return x*len;}

inline bool cmp(question x,question y){
	if(x.pos!=y.pos) return x.pos<y.pos;
	if(x.pos&1) return x.r<y.r;
	return x.r>y.r;
}

struct S_sqrt{
	int a[N],b[SQ];
	inline void add(int x,int k){
		if(x==0){cnt[0]+=k;return ;}
		if(k==1){
			if(cnt[x]++==0) a[x]++,b[block(x)]++;
		}
		else{
			if(--cnt[x]==0) a[x]--,b[block(x)]--;
		}
	}
	inline int mex(){
		if(cnt[0]==0) return 0;
		int nw=1;
		while(b[nw]==len) ++nw;
		for(re i=L(nw);1;++i) if(cnt[i]==0) return i;
	}
}A;

// ----------  ---------- //

int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	rd(n);rd(m);len=(int)sqrt(n);
	for(re i=1;i<=n;++i) rd(s[i]);
	for(re i=1;i<=m;++i) rd(q[i].l),rd(q[i].r),q[i].id=i,q[i].pos=block(q[i].l);
	sort(q+1,q+m+1,cmp);
	int l=q[1].l+1,r=q[1].l;
	for(re i=1;i<=m;++i){
		while(l>q[i].l) A.add(s[--l],1);
		while(r<q[i].r) A.add(s[++r],1);
		while(l<q[i].l) A.add(s[l++],-1);
		while(r>q[i].r) A.add(s[r--],-1);
		ans[q[i].id]=A.mex();
	}
	for(re i=1;i<=m;++i) wr(ans[i]),puts("");
	return 0;
}

// ---------- Main ---------- //