难受，自己手造值域巨大的小数据都没挂

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;

struct query {
	int t;
	int l,r;
	int l_block;
	int r_block;
};

query q[N];
int n,m;
int a[N];
vector<int>b[N];
int ans[N];
int c[N];
int d[N];
int f[N];
int p[N];
int e[N*2];
int cnt=0;
int maxn=0;
int l,r,t;
int block;

bool cmp (query x,query y) {
	if(x.l_block!=y.r_block) return x.l_block<y.r_block;
	if(x.r_block!=y.r_block) return x.r_block<y.r_block;
	return x.t<y.t;
}

void add_pos(int x) {
	int k=a[x];
	d[c[k]++]--;
	d[c[k]]++;
}

void del_pos(int x) {
	int k=a[x];
	d[c[k]--]--;
	d[c[k]]++;
}

void add_time(int t) {
	int k=f[t];
	if(k==0) return ;
	if(k>=l&&k<=r) del_pos(k),a[k]=b[k][++p[k]],add_pos(k);
	else a[k]=b[k][++p[k]];
}

void del_time(int t) {
	int k=f[t];
	if(k==0) return ;
	if(k>=l&&k<=r) del_pos(k),a[k]=b[k][--p[k]],add_pos(k);
	else a[k]=b[k][--p[k]];
}

int mex() {
	int k=0;
	while(1) {
		if(d[k]==0) return k;
		k++;
	}
}

int main() {
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		scanf("%d",&a[i]),b[i].push_back(a[i]),e[i]=a[i];

	int maxn=n;
	block=max(10,(int)pow(n,2.0/3.0));
	for(int i=1; i<=m; i++) {
		int opt,l,r;
		scanf("%d",&opt);
		if(opt==1) {
			scanf("%d%d",&l,&r);
			q[++cnt].l=l;
			q[cnt].r=r;
			q[cnt].t=i;
			q[cnt].l_block=(l-1)/block+1;
			q[cnt].r_block=(r-1)/block+1;
		}
		if(opt==2) {
			scanf("%d%d",&l,&r);
			f[i]=l;
			b[l].push_back(r);
			e[++maxn]=r;
		}
	}
	sort(e+1,e+1+maxn);
	maxn=unique(e+1,e+1+maxn)-e-1;
	for(int i=1; i<=n; i++)
		a[i]=lower_bound(e+1,e+1+maxn,a[i])-e;
	for(int i=1; i<=n; i++)
		for(int j=0; j<b[i].size(); j++)
			b[i][j]=lower_bound(e+1,e+1+maxn,b[i][j])-e;
	sort(q+1,q+1+cnt,cmp);
	l=1,r=0,t=0;
	d[0]=1e9;
	memset(ans,-1,sizeof(ans));
	for(int i=1; i<=cnt; i++) {
		while(r<q[i].r) add_pos(++r);
		while(r>q[i].r) del_pos(r--);
		while(l<q[i].l) del_pos(l++);
		while(l>q[i].l) add_pos(--l);
		while(t<q[i].t) add_time(++t);
		while(t>q[i].t) del_time(t--);
		ans[q[i].t]=mex();
	}
	for(int i=1; i<=m; i++)
		if(ans[i]!=-1)
			printf("%d\n",ans[i]);
	return 0;
}