CF上 #3 就 $\small\text {WA}$ 了,样例没有问题,求查错/kel/kel/kel

#include<bits/stdc++.h>
#define N 100010
using namespace std;
inline int read(void) {
	register int x=0;
	register short sgn=1;
	register char c=getchar();
	while(c<48||57<c) {
		if(c==45) sgn=0;
		c=getchar();
	}
	while(47<c&&c<58) {
		x=(x<<3)+(x<<1)+c-48;
		c=getchar();
	}
	return sgn? x:-x;
}
struct rrank {
	int a;
	int *id;
	int typ;
	inline bool operator < (const rrank x) const {
		return a<x.a;
	}
} rnk[N<<1];
struct query {
	int d;
	int l,r;
	int idt;
	int lbl;
	int rbl;
	inline bool operator < (const query x) const {
		return lbl^x.lbl ? lbl<x.lbl : ( rbl^x.rbl ? rbl<x.rbl : ( d^x.d ? d<x.d : ((r<x.r)^(lbl&1)) ) );
	}
} qry[N];
struct updat {
	int pos;
	int trf;
} upd[N]; 
int exist[N];
int cnt[N];
int ans[N];
int srl[N];
int cntdfn;
int cntidt;
int n,m;
inline void add(int i) {
	--exist[cnt[srl[i]]];
	++cnt[srl[i]];
	++exist[cnt[srl[i]]];
}
inline void del(int i) {
	--exist[cnt[srl[i]]];
	--cnt[srl[i]];
	++exist[cnt[srl[i]]];
}
inline void rep(int i,int dfn) {
	if(qry[i].l<=upd[dfn].pos && upd[dfn].pos<=qry[i].r) {
		del(upd[dfn].pos);
		swap(srl[upd[dfn].pos],upd[dfn].trf);
		add(upd[dfn].pos);
	} else swap(srl[upd[dfn].pos],upd[dfn].trf);
}
signed main() {
	n=read(),m=read();
	register int type;
	for(register int i=1; i<=n; ++i) rnk[i].a=read(),rnk[i].id=&srl[i],rnk[i].typ=1;
	for(register int i=1; i<=m; ++i) {
		type=read();
		if(type==1) {
			++cntidt;
			qry[cntidt].idt=cntidt;
			qry[cntidt].l=read();
			qry[cntidt].r=read();
			qry[cntidt].d=cntdfn;
			qry[cntidt].lbl=qry[cntidt].l>>9;
			qry[cntidt].rbl=qry[cntidt].r>>9;
		} else {
			++cntdfn;
			upd[cntdfn].pos=read();
			rnk[n+cntdfn].a=read();
			rnk[n+cntdfn].id=&upd[cntdfn].trf; 
		}
	}
	sort(qry+1,qry+cntidt+1);
	sort(rnk+1,rnk+n+cntdfn+1);
	for(register int i=1; i<=n+cntdfn; ++i) {
		if(rnk[i].a==rnk[i-1].a) *rnk[i].id=*rnk[i-1].id;
		else *rnk[i].id=i;
	}
	
	register int l=1,r=0,t=0,nas=1;
	for(register int i=1; i<=cntidt; ++i,nas=1) {
		if(!qry[i].idt) continue;
		while(l>qry[i].l) add(--l);
		while(r<qry[i].r) add(++r);
		while(l<qry[i].l) del(l++);
		while(r>qry[i].r) del(r--);
		while(t>qry[i].d) rep(i,t--);
		while(t<qry[i].d) rep(i,++t);
		while(exist[nas])      ++nas;
		ans[qry[i].idt]=nas;
	}
	for(register int i=1; i<=cntidt; ++i) 
		printf("%d\n",ans[i]); 
}