P1903 [国家集训队] 数颜色 / 维护队列 - 洛谷 | 计算机科学教育新生态
额好像是修改写错了，今天太晚了明天调下吧
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
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;
}
struct node{
int l,r,t,id;
}q[N];
struct node2{
int p,val;
}c[N];
int block,pos[N],a[N],n,m;
int cntq,cntc,cnt[N];
int Ans,ans[N];
inline bool mdcmp(node a,node b){
if(pos[a.l]!=pos[b.l]) return a.l<b.l;
if(pos[a.r]!=pos[b.r]) return a.r<b.r;
return a.t<b.t;
}
inline void add(int i){
cnt[a[i]]++;
if(cnt[a[i]]==1) Ans++;
}
inline void del(int i){
cnt[a[i]]--;
if(cnt[a[i]]==0) Ans--;
}
inline void change(int cg,int i){
if(q[i].l<=c[cg].p&&c[cg].p<=q[i].r){//只有修改的值在区间里面才能产生贡献
del(c[cg].p);
cnt[c[cg].val]++;
if(cnt[c[cg].val]==1) Ans++;
}
swap(a[c[cg].p],c[cg].val);//交换颜色，下次回退的时候就能直接换回来了
}
int main(){
cin>>n>>m;
block=pow(double(n),2.0/3.0);
//cout<<block<<endl;
for(int i=1;i<=n;i++){
a[i]=read();
pos[i]=(i-1)/block;
}
for(int i=1;i<=m;i++){
int x,y;char op;
scanf("%s",&op);
x=read(),y=read();
if(op=='Q'){
q[++cntq].l=x;
q[cntq].r=y;
q[cntq].t=cntc;
q[cntq].id=cntq;
}
else{
c[++cntc].p=x;
c[cntc].val=y;
}
}
sort(q+1,q+cntq+1,mdcmp);
int L=1,R=0,T=0;
for(int i=1;i<=cntq;i++){
while(L<q[i].l) del(L++);
while(R>q[i].r) del(R--);
while(T>q[i].t) change(T--,i);
while(L>q[i].l) add(--L);
while(R<q[i].r) add(++R);
while(T<q[i].t) change(++T,i);
ans[q[i].id]=Ans;
}
for(int i=1;i<=cntq;i++){
cout<<ans[i]<<endl;
}
return 0;
}