RT，

跟着这篇博客学的

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
#define int long long
#define mod 998244353
#define MAXN 1000001
using namespace std;
int n,m,b;
int a[MAXN],p[MAXN],ans;//值的出现次数
int u,j,o[MAXN];//询问的答案
pair<int,int> c[MAXN];//first修改的位置,second修改的值
int idb(int x){
	return x/b;
}
struct  kx{
	int l,r,id,t;//这个询问值的修改次数，id为查询次数
	bool operator <(const kx &tmp) const{
		if(idb(l)==idb(tmp.l)){
			if(idb(r)==idb(tmp.r)) return t<tmp.t;
			return r<tmp.r;
		}
		return l<tmp.l;
	}
};
kx k[MAXN];
bool cmp(kx x,kx y){
	return x<y;
}
void add(int x){
	p[x]++;
	if(p[x]==1) ans++;
}
void del(int x){
	p[x]--;
	if(p[x]==0) ans--;
}
signed main(){
	ios::sync_with_stdio(false); 
	cin>>n>>m;
	double g=pow(n,(double)2/3);
	b=g;
	cout<<b;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=m;i++){
		char t;
		cin>>t;
		if(t=='Q'){
			u++;
			cin>>k[u].l>>k[u].r;
			k[u].id=u;
			k[u].t=j;
		}else{
			int x,y;
			cin>>x>>y;
			j++;
			c[j]=make_pair(x,y);
		}
	}
	sort(k+1,k+1+u,cmp);
	int sl=1,sr=0,st=0;
	for(int i=1;i<=u;i++){
		while(sl>k[i].l) add(a[--sl]);
		while(sr<k[i].r) add(a[++sr]);
		while(sl<k[i].l) del(a[sl++]);
		while(sr>k[i].r) del(a[sr--]);
		while(st<k[i].t){
			int tmp=a[c[++st].first];
			a[c[st].first]=c[st].second;
			if(c[st].first>=k[i].l&&c[st].first<=k[i].r) add(a[c[st].first]);
			c[st].second=tmp;
			if(c[st].first>=k[i].l&&c[st].first<=k[i].r) del(c[st].second);
		}
		while(st>k[i].t){
			int tmp=a[c[st].first];
			a[c[st].first]=c[st].second;
			if(c[st].first>=k[i].l&&c[st].first<=k[i].r) add(a[c[st].first]);
			c[st].second=tmp;
			if(c[st].first>=k[i].l&&c[st].first<=k[i].r) del(c[st].second);
			st--;
		}
		o[k[i].id]=ans;
	}
	for(int i=1;i<=u;i++){
		cout<<o[i]<<"\n";
	}
	return 0;
}