[Codeforces Round #466 (Div.2)] 940F-Machine Learning

题目（Codeforces）
 
带修改莫队真的很快......
先按pos[x.l]排序，再按pos[x.r]排序，最后按x.t排序
（因为我排序方式不佳所以T成狗）

#include <bits/stdc++.h>
using namespace std;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=100050;
int pos[N],a[N],sz,n,Q,has,cnt[N],now[N],cntq,vis[N<<1];
map <int,int> mp;
int L=1,R;
struct querys{
	int t,l,r;
	int id;
}q[N];
struct updata{
	int p,v,y;
}c[N];
inline bool cmp(const querys &x,const querys &y){
	if(pos[x.l]==pos[y.l]&&pos[x.r]==pos[y.r])return x.t<y.t;
	else if(pos[x.l]==pos[y.l])return pos[x.r]<pos[y.r];
	else return pos[x.l]<pos[y.l];
}
int ans[N],tim;
inline void ad(int x){
	int &y=vis[x];
	if(y>0)cnt[y]--;
	y++;
	if(y>0)cnt[y]++;
}
inline void de(int x){
	int &y=vis[x];
	if(y>0)cnt[y]--;
	y--;
	if(y>0)cnt[y]++;
}
inline void addt(int t){
	int p=c[t].p,v=c[t].v;
	if(L<=p&&p<=R){
		de(a[p]);
		ad(v);
	}
	a[p]=v;
}
inline void delt(int t){
	int p=c[t].p,v=c[t].y;
	if(L<=p&&p<=R){
		de(a[p]);
		ad(v);
	}
	a[p]=v;
}
int main(){
	read(n),read(Q);sz=2000;
	for(int i=1;i<=n;++i){
		read(a[i]);
		if(!mp[a[i]])mp[a[i]]=++has;
		now[i]=a[i]=mp[a[i]];
		pos[i]=i/sz+1;
	}
	for(int i=1;i<=Q;++i){
		int opt,x,y;
		read(opt),read(x),read(y);
		if(opt==1){
			++cntq;q[cntq]=(querys){tim,x,y,cntq};
		}
		else{
			if(!mp[y])mp[y]=++has;y=mp[y];
			++tim;
			c[tim]=(updata){x,y,now[x]};
			now[x]=y;
		}
	}
	tim=0;
	sort(q+1,q+cntq+1,cmp);
	for(int i=1;i<=cntq;++i){
		while(tim<q[i].t)++tim,addt(tim);
		while(tim>q[i].t)delt(tim),--tim;
		while(L<q[i].l)de(a[L]),++L;
		while(R>q[i].r)de(a[R]),--R;
		while(L>q[i].l)--L,ad(a[L]);
		while(R<q[i].r)++R,ad(a[R]);
		for(int j=1;;++j)if(!cnt[j]){ans[q[i].id]=j;break;}
	}
	for(int i=1;i<=cntq;++i)printf("%d\n",ans[i]);
	return 0;
}