带修莫队
#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
int a[maxn],x[maxn],res[maxn],cnt[maxn],ans;
char op;
struct quest{
int l,r,tim,id;
}q[maxn];
struct Node{
int pos,val;
}d[maxn];
bool cmp(quest a,quest b){
if(x[a.l]!=x[b.l]) return x[a.l]<x[b.l];
if(x[a.r]!=x[b.r]) return x[a.r]<x[a.r];
return a.tim<b.tim;
}
void add(int u){
if(++cnt[a[u]]==1) ans++;
}
void del(int u){
if(--cnt[a[u]]==0) ans--;
}
void upd(int tim,int i){
if(d[tim].pos>=q[i].l&&d[tim].pos<=q[i].r){
if((--cnt[a[d[tim].pos]])==0) ans--;
if((++cnt[d[tim].val])==1) ans++;
}
swap(d[tim].val,a[d[tim].pos]);
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n,m,l,r,size,TIME,CNT,now;
while(cin>>n>>m){
size=pow(n,0.666);
for(register int i=1;i<=n;i++)
cin>>a[i],x[i]=(i-1)/size+1;
TIME=0; CNT=0;
for(register int i=1;i<=m;i++){
cin>>op;
if(op=='Q'){
CNT++;
cin>>q[CNT].l>>q[CNT].r;
q[CNT].id=CNT; q[CNT].tim=TIME;
}
if(op=='R'){
TIME++;
cin>>d[TIME].pos>>d[TIME].val;
}
}
sort(q+1,q+CNT+1,cmp);
l=1; r=0; now=0; ans=0;
memset(cnt,0,sizeof(cnt));
for(register int i=1;i<=CNT;i++)
{
int ql=q[i].l,qr=q[i].r,qt=q[i].tim;
while(l<ql) del(l++);
while(l>ql) add(--l);
while(r<qr) add(++r);
while(r>qr) del(r--);
while(now<qt) upd(++now,i);
while(now>qt) upd(now--,i);
res[q[i].id]=ans;
}
for(register int i=1;i<=CNT;i++)
cout<<res[i]<<endl;
}
}
58分,蒟蒻不会卡常QAQ
请求大佬教教