rt,在学校自己的OJ上A了

#include <bits/stdc++.h>
#pragma GCC optimeze(3)
#pragma GCC optimeze(2)
#define int long long
using namespace std;
const int N=2e6+5;
int read(){
	int x=0,flag=1;
	char ch=0;
	while(ch<'0'||ch>'9'){
		if(ch=='-')flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*flag;
}
struct query{
	int l,r,bl,bh,br,t;
}q[N];
struct xg{
	int x,y,dy;
}g[N];
int n,a[N],m,k,ans[N],mjl,sumg=0,sumq=0,help[N],len,dy[N];
int b[N],c[N];
bool cmp(query a,query b){
	if(a.bl!=b.bl)return a.bl<b.bl;
	if(a.br!=b.br)return a.br<b.br;
	return a.t<b.t;
}
void add(int x){
	c[b[x]]--;
	b[x]++;
	c[b[x]]++;
}
void del(int x){
	c[b[x]]--;
	b[x]--;
	c[b[x]]++;
}
void upd(int x,int t){
	if(q[x].l<=g[t].x&&q[x].r>=g[t].x){
		del(dy[g[t].x]);
		add(g[t].dy);
	}
	swap(dy[g[t].x],g[t].dy);
}
signed main() {
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		help[++len]=a[i];
	}
	int kk=pow(n,0.666);
	for(int i=1;i<=m;i++){
		int op;
		op=read();
		if(op==1){
			sumq++;
			q[sumq].l=read(),q[sumq].r=read(),q[sumq].bh=sumq,q[sumq].bl=(q[sumq].l-1)/kk+1,q[sumq].br=(q[sumq].r-1)/kk+1,q[sumq].t=sumg;
		}
		else{
			sumg++;
			g[sumg].x=read(),g[sumg].y=read();
			help[++len]=g[sumg].y;
		}
	}
	sort(help+1,help+1+len);
	len=unique(help+1,help+1+len)-help-1;
	for(int i=1;i<=sumg;i++){
		g[i].dy=lower_bound(help+1,help+1+len,g[i].y)-help;
	}
	for(int i=1;i<=n;i++){
		dy[i]=lower_bound(help+1,help+1+len,a[i])-help;
	}
	sort(q+1,q+1+sumq,cmp);
	int l=1,r=0,t=0;
	for(int i=1;i<=sumq;i++){
		while(l<q[i].l)del(dy[l++]);
		while(l>q[i].l)add(dy[--l]);
		while(r<q[i].r)add(dy[++r]);
		while(r>q[i].r)del(dy[r--]);
		while(t<q[i].t)upd(i,++t);
		while(t>q[i].t)upd(i,t--);
		int sum=1;
		while(c[sum])sum++;
		ans[q[i].bh]=sum;
	}
	for(int i=1;i<=sumq;i++){
		printf("%lld\n",ans[i]);
	}
    return 0;
}