RT，讨论区都看过一遍了还没找到原因。。。

code:

#include<algorithm>
#include<cstdio>
#include<cmath>
const int M=1e5+5;
int n,m,p,len,cnt1,cnt2,a[M],lsh[M],ans[M];
int CB[M],num[M];
int L=1,R=0,t=0;
struct Query{
	int L,R,t,p1,p2,id;
	inline bool operator<(const Query&it)const{
		return p1==it.p1?p2==it.p2?t<it.t:R<it.R:L<it.L;
	}
}q[M];
struct Mdf{
	int id,val;
}mdf[M];
inline void swap(int&x,int&y){
	x^=y^=x^=y;
}
inline void Add(const int&val){
	--CB[num[val]];++CB[++num[val]];
}
inline void Del(const int&val){
	--CB[num[val]];++CB[--num[val]];
}
inline void Modify(const int&id){
	if(L<=mdf[id].id&&mdf[id].id<=R){
		Del(a[mdf[id].id]);Add(mdf[id].val);
	}
	swap(a[mdf[id].id],mdf[id].val);
}
inline int Q(){
	int ans=1;
	while(CB[ans++]);
	return --ans;
}
signed main(){
	register int i,f;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)scanf("%d",a+i),lsh[++len]=a[i];
	std::sort(lsh+1,lsh+len+1);len=std::unique(lsh+1,lsh+len+1)-lsh-1;
	for(i=1;i<=n;++i)a[i]=std::lower_bound(lsh+1,lsh+len+1,a[i])-lsh;
	for(i=1;i<=m;++i){
		scanf("%d",&f);
		if(f==1){
			++cnt1;
			scanf("%d%d",&q[cnt1].L,&q[cnt1].R);q[cnt1].t=cnt2;q[cnt1].id=cnt1;
		}
		else{
			++cnt2;
			scanf("%d%d",&mdf[cnt2].id,&mdf[cnt2].val);
		}
	}
	p=ceil(n/sqrt(2.0*cnt1/3));
	for(i=1;i<=cnt1;++i)q[i].p1=q[i].L/p,q[i].p2=q[i].R/p;
	std::sort(q+1,q+cnt1+1);
	for(i=1;i<=cnt1;++i){
		const int&QL=q[i].L,&QR=q[i].R,&QT=q[i].t;
		while(R<QR)Add(a[++R]);
		while(L>QL)Add(a[--L]);
		while(L<QL)Del(a[L++]);
		while(R>QR)Del(a[R--]);
		while(t<QT)Modify(++t);
		while(t>QT)Modify(t--);
		ans[q[i].id]=Q();
	}
	for(i=1;i<=cnt1;++i)printf("%d\n",ans[i]);
}