rt，测评记录

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct data1
{
	int l,r,tim,id;
}x[N];
struct data2
{
	int id,col;
}y[N];
char op;
int n,m,a[N],u,v,tot1,tot2,siz,num[N],ans[N],l,r,t,tmp,cnt[N];
inline bool cmp(data1 x,data1 y)
{
	if(num[x.l]!=num[y.l])
		return num[x.l]<num[y.l];
	if(num[x.l]%2==1)
        return x.r<y.r;
    return x.r>y.r; 
}
inline void add(int col)
{
	if(cnt[col]==0)
		tmp++;
	cnt[col]++;
}
inline void del(int col)
{
	cnt[col]--;
	if(cnt[col]==0)
		tmp--;
}
inline void updata(int id,int i)
{
	if(x[i].l<=y[id].id&&y[id].id<=x[i].r)
	{
		add(y[id].col);
		del(a[y[id].id]);
	}
	swap(y[id].col,a[y[id].id]);
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
	cin>>n>>m;
	siz=pow(n,0.667);
	for(register int i=1;i<=n;i++)
	{
		cin>>a[i];
		num[i]=(i-1)/siz+1;
	}
	for(register int i=1;i<=m;i++)
	{
		cin>>op>>u>>v;
		if(op=='Q')
			x[++tot1]=(data1){u,v,tot2,tot1};
		else y[++tot2]=(data2){u,v}; 
	}
	sort(x+1,x+tot1+1,cmp);
	l=1;
	for(register int i=1;i<=tot1;i++)
	{
		while(l>x[i].l)add(a[--l]);
		while(r<x[i].r)add(a[++r]);
		while(l<x[i].l)del(a[l++]);
		while(r>x[i].r)del(a[r--]);
		while(t<x[i].tim)updata(++t,i);
		while(t>x[i].tim)updata(t--,i);
		ans[x[i].id]=tmp;
	}
	for(register int i=1;i<=tot1;i++)
		cout<<ans[i]<<'\n';
	return 0;
}