IV.III.[国家集训队]数颜色 / 维护队列
虽然这里这题的写法是CDQ但是我还是要大声喊出：树套树yyds！
首先，众所周知地，我们可以对于每个位置记录其颜色上一次出现的地方，记作 \(las_i\)，则我们需要知道的就是 \([l,r]\) 中 \(las_i<l\) 的总数。
众所周知地，这是二维数点问题。现在有了修改操作，需要保证时间顺序，因此变成了大家都喜欢的三维数点问题。
具体操作很简单：因为观察到一次修改最多改变 \(3\) 个位置的 \(las\) 值，放到二维数点的平面上就是 \(6\) 次修改，于是预处理这六次修改的样式，然后CDQ分治时计算左侧的修改对右侧询问的影响就行了。可以采用树状数组简单处理。
但是CDQ分治也有其优点，就是空间复杂度是 \(O(n)\)。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,a[150010],lim,las[150010],res[150010],t[150010];
vector<int>v;
struct node{
int tp,a,b;
node(){}
node(int T,int A,int B){tp=T,a=A,b=B;}
friend bool operator<(const node&x,const node&y){return x.a==y.a?!x.tp>!y.tp:x.a<y.a;}
}q[150010];
char str[10];
set<int>s[300010];
void ADD(int x,int y){while(x<=n)t[x]+=y,x+=x&-x;}
int SUM(int x){int ret=0;while(x)ret+=t[x],x-=x&-x;return ret;}
vector<node>u,w[150010];
void CDQ(int l,int r){
if(l==r)return;
int mid=(l+r)>>1;
for(int i=l;i<=mid;i++)if(!q[i].tp)for(auto j:w[i])u.push_back(j);
for(int i=mid+1;i<=r;i++)if(q[i].tp)for(auto j:w[i])u.push_back(j);
sort(u.begin(),u.end());
for(auto i:u){
if(!i.tp){
if(i.b>0)ADD(i.b,1);
else ADD(-i.b,-1);
}else{
if(i.tp>0)res[i.tp]+=SUM(i.b);
else res[-i.tp]-=SUM(i.b);
}
}
u.clear();
for(auto i:u)if(!i.tp){
if(i.b>0)ADD(i.b,-1);
else ADD(-i.b,1);
}
CDQ(l,mid),CDQ(mid+1,r);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),v.push_back(a[i]);
for(int i=1;i<=m;i++){
scanf("%s%d%d",str,&q[i].a,&q[i].b),q[i].tp=(str[0]=='Q');
if(str[0]=='R')v.push_back(q[i].b);
}
sort(v.begin(),v.end()),v.resize(lim=unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=n;i++)s[a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1].insert(i);
for(int i=1;i<=m;i++)if(!q[i].tp)q[i].b=lower_bound(v.begin(),v.end(),q[i].b)-v.begin()+1;
for(int i=1;i<=n;i++){
auto tmp=s[a[i]].lower_bound(i);
if(tmp!=s[a[i]].begin())las[i]=1+*--tmp;
else las[i]=1;
}
for(int i=1;i<=m;i++){
if(!q[i].tp)continue;
u.emplace_back(-i,q[i].a-1,q[i].a),u.emplace_back(i,q[i].b,q[i].a);
w[i].emplace_back(-i,q[i].a-1,q[i].a),w[i].emplace_back(i,q[i].b,q[i].a);
}
sort(u.begin(),u.end());
for(int i=0,j=1;i<u.size();i++){
while(j<=u[i].a)ADD(las[j++],1);
if(u[i].tp>0)res[u[i].tp]+=SUM(u[i].b);else res[-u[i].tp]-=SUM(u[i].b);
}
u.clear(),memset(t,0,sizeof(t));
for(int i=1;i<=m;i++){
if(q[i].tp)continue;
int P=q[i].a,C=q[i].b;
if(C==a[P])continue;
w[i].emplace_back(0,P,-las[P]);
s[a[P]].erase(P);
auto tmp=s[a[P]].lower_bound(P);
if(tmp!=s[a[P]].end())w[i].emplace_back(0,*tmp,-las[*tmp]),w[i].emplace_back(0,*tmp,las[*tmp]=las[P]);
tmp=s[C].lower_bound(P);
if(tmp!=s[C].end()){
w[i].emplace_back(0,P,las[P]=las[*tmp]);
w[i].emplace_back(0,*tmp,-las[*tmp]);
w[i].emplace_back(0,*tmp,las[*tmp]=P+1);
}else if(tmp!=s[C].begin())w[i].emplace_back(0,P,las[P]=1+*--tmp);
else w[i].emplace_back(0,P,las[P]=1);
a[P]=C;
s[C].insert(P);
}
CDQ(1,m);
for(int i=1;i<=m;i++)if(q[i].tp)printf("%d\n",res[i]);
return 0;
}