数颜色 HYSBZ

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2*1e6+10;
int ans[maxn],cnt[maxn],Ans = 0;
int a[maxn],belong[maxn];
struct xx
{
	int l,r,id,time;
} Q[maxn];
struct change
{
	int pos,val;
} cge[maxn];
int n,m;
inline int read()
{
	char c=getchar();
	int x=0,f=1;
	while(c<'0'||c>'9')
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')
	{
		x=x*10+c-'0',c=getchar();
	}
	return x*f;
}
inline bool cmp(xx A,xx B)
{
	if(belong[A.l] != belong[B.l])
		return belong[A.l] < belong[B.l];
	if(belong[A.r] != belong[B.r])
		return belong[A.r] < belong[B.r];
	return A.time < B.time;
}
inline void add(int x)
{
	if(!cnt[a[x]])
		++ Ans;
	++ cnt[a[x]];
}
inline void del(int x)
{
	if(cnt[a[x]] == 1)
		-- Ans;
	-- cnt[a[x]];
}
inline void update(int i,int _time)
{
	if(cge[_time].pos >= Q[i].l && cge[_time].pos <= Q[i].r)
		del(cge[_time].pos);
	swap(cge[_time].val,a[cge[_time].pos]);
	if(cge[_time].pos >= Q[i].l && cge[_time].pos <= Q[i].r)
		add(cge[_time].pos);
}
int main()
{
	int n=read(),m=read() ;
	int block = pow(n,0.666);
	for(int i = 1; i <= n; ++ i)
	{
		a[i]=read();
		belong[i] = (i - 1) / block + 1;
	}
	int tmp = 0,pq = 0;
	for(int i = 1; i <= m; ++ i)
	{
		char op;
		scanf(" %c",&op);
		//如果是查询
		if(op == 'Q')
		{
			//记录查询的
			Q[++ pq].l=read();
			Q[pq].r=read();
			Q[pq].id = pq;
			//时间点  ，在第几次更新之前
			Q[pq].time = tmp;
		}
		//如果是更新的话
		else
		{
			//记录更新
			cge[++ tmp].pos=read();
			cge[tmp].val=read();
		}
	}
	sort(Q + 1,Q + 1 + pq,cmp);
	int L = 1,R = 0,_time = 0;
	for(int i = 1; i <= pq; ++ i)
	{
		while(L < Q[i].l)
			del(L ++);
		while(L > Q[i].l)
			add(-- L);
		while(R < Q[i].r)
			add(++ R);
		while(R > Q[i].r)
			del(R --);
		while(_time > Q[i].time)
			update(i,_time --);
		while(_time < Q[i].time)
			update(i,++ _time);
		ans[Q[i].id] = Ans;
	}
	for(int i = 1; i <= pq; ++ i)
		printf("%d
",ans[i]);
	return 0;
}