区间数颜色和单点修改。
可以树套树，但是不太会。
也可以考虑带修莫队，相当于就是多维护了一个时间轴。
排序方法变成先按块排序 (l,r) ，再按照 (t) 来排序即可。
单点修改里的 (swap) 很妙。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005,M=1000005;
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-'){f=-1;}ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int a[N],pos[N],n,m,ANS[N],ans,cnt[N],cnt1,cnt2,l=1,r;
struct node{int ql,qr,t,id;}q[N];
struct node1{int p,x;}c[N];
inline bool cmp(node x,node y){
if(pos[x.ql]!=pos[y.ql])return x.ql<y.ql;
if(pos[x.qr]!=pos[y.qr])return x.qr<y.qr;
return x.t<y.t;
}
inline void update(int id,int f){
int x=a[id];
cnt[x]+=f;
if(f==1&&cnt[x]==1) ans++;
if(f==-1&&cnt[x]==0) ans--;
return ;
}
inline void change(int id){
if(c[id].p>=l&&c[id].p<=r){
cnt[a[c[id].p]]--;
if(cnt[a[c[id].p]]==0) ans--;
if(cnt[c[id].x]==0) ans++;
cnt[c[id].x]++;
}
swap(c[id].x,a[c[id].p]);
return ;
}
signed main(){
n=read(),m=read();
int op=pow(n,2.0/3.0);
for(int i=1;i<=n;i++){
a[i]=read();
pos[i]=i/op;
}
for(int i=1;i<=m;i++){
char oop[2];
scanf("%s",oop+1);
if(oop[1]=='Q') q[++cnt1].ql=read(),q[cnt1].qr=read(),q[cnt1].id=cnt1,q[cnt1].t=cnt2;
else c[++cnt2].p=read(),c[cnt2].x=read();
}
sort(q+1,q+cnt1+1,cmp);
for(int i=1,t=0;i<=m;i++){
while(l<q[i].ql) update(l++,-1);
while(l>q[i].ql) update(--l,1);
while(r<q[i].qr) update(++r,1);
while(r>q[i].qr) update(r--,-1);
while(t<q[i].t) change(++t);
while(t>q[i].t) change(t--);
ANS[q[i].id]=ans;
}
for(int i=1;i<=cnt1;i++) printf("%d
",ANS[i]);
return 0;
}