安利一下既好写又美观的树套树（大雾
思路和HH的项链一样，维护每个位置下一个和它相同颜色的位置$nex[i]$，查询时就找$nex[i]>R$且$L\le i\le R$的个数（$[L,R]$为待查询区间，下同）。
两个限制条件自然想到树套树。外层用线段树或树状数组维护$nex[i]$，每个节点内部开一个平衡树或动态开点线段树维护位置。查询时直接查外层$[R+1,n+1]$（这里提前把$nex[i]$为$0$的都改为$n+1$）中，内层位于$[L,R]$的数量。
不过修改比较麻烦：
记$i$为修改点，$last$为上一个和$i$颜色相同的位置（可以开数组记下来，想偷懒的话直接开平衡树查也行），$j$为$i$前面第一个颜色为要修改的颜色的位置，二元组$(x,y)$为外层为$x$，内层为$y$。修改操作就为：
- 删除$(i,last)$
- 插入$(nex[i],last)$
- 赋值$nex[last]=nex[i]$
- 删除$(nex[i],i)$
- 插入$(nex[j],i)$
- 删除$(nex[j],j)$
- 插入$(i,j)$
- 赋值$nex[i]=nex[j],nex[j]=i$
不理解的话可以画个图，观察一下一次修改操作会对$last,nex[i],j,nex[j]$产生的影响。
因为有可能$j$或$last$为$0$，需要记一下每种颜色当前第一次出现的位置，判断修改。
线段树套线段树$2900ms$（$O_2$），树状数组套线段树$1300ms$（$O_2$）
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 50005
#define inf 0x3f3f3f3f
using namespace std;
inline int read(){
int x=0,y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
template<typename T>
inline T read(){
T x=0;
int y=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return y?-x:x;
}
inline int ran(){
static int seed=45562;
return seed=(seed*48271LL%2147483647);
}
int n;
#define ls(x) ls[x]
#define rs(x) rs[x]
struct Treap{
int dat[maxn<<2],ls[maxn<<2],rs[maxn<<2],siz[maxn<<2],ra[maxn<<2],cnt;
inline void update(int node){
siz[node]=siz[ls(node)]+siz[rs(node)]+1;
}
void right(int &node){
int rec=ls(node);
ls(node)=rs(rec);
rs(rec)=node;
node=rec;
update(rs(node)),update(node);
}
void left(int &node){
int rec=rs(node);
rs(node)=ls(rec);
ls(rec)=node;
node=rec;
update(ls(node)),update(node);
}
void insert(int &node,int d){
if(!node){
node=++cnt;
ra[node]=ran(),dat[node]=d,siz[node]=1;
return;
}
if(dat[node]<d){
insert(rs(node),d);
if(ra[rs(node)]>ra[node])left(node);
}
else {
insert(ls(node),d);
if(ra[ls(node)]>ra[node])right(node);
}
++siz[node];
}
void del(int &node,int d){
if(dat[node]==d){
if(ls(node)&&rs(node)){
if(ra[ls(node)]>ra[rs(node)])right(node),del(rs(node),d);
else left(node),del(ls(node),d);
--siz[node];
}
else node=ls(node)|rs(node);
return;
}
if(dat[node]<d)del(rs(node),d);
else del(ls(node),d);
--siz[node];
}
int getpre(int node,int d){
int ans=0;
while(node){
if(dat[node]<d)ans=max(ans,dat[node]),node=rs(node);
else node=ls(node);
}
return ans;
}
}tr;
struct Data_Segment_Tree{
int ls[maxn<<5],rs[maxn<<5],sum[maxn<<5],cnt;
void add(int poi,int l,int r,int &node,int d){
if(!node)node=++cnt;
sum[node]+=d;
if(l==r)return;
int mid=l+r>>1;
if(poi<=mid)add(poi,l,mid,ls(node),d);
else add(poi,mid+1,r,rs(node),d);
}
int ask(int L,int R,int l,int r,int node){
if(!node)return 0;
if(L<=l&&R>=r)return sum[node];
int mid=l+r>>1,ans=0;
if(L<=mid)ans=ask(L,R,l,mid,ls(node));
if(R>mid)ans+=ask(L,R,mid+1,r,rs(node));
return ans;
}
}dst;
#undef ls
#undef rs
/*==============树状数组套线段树===============*/
struct Binary_Indexed_Tree{
int root[maxn];
#define lowb(x) (x&-x)
inline void add(int x,int pl,int d){
while(x<=n+1)dst.add(pl,1,n,root[x],d),x+=lowb(x);
}
inline int ask(int x,int l,int r){
int ans=0;
while(x)ans+=dst.ask(l,r,1,n,root[x]),x-=lowb(x);
return ans;
}
}bit;
int root[1000005],fir[1000005],nex[maxn],pre[1000005],a[maxn];
inline void change(int i,int d){
if(a[i]==d)return;
int last=tr.getpre(root[a[i]],i),j=tr.getpre(root[d],i);
if(fir[a[i]]==i)fir[a[i]]=nex[i];
if(last){
bit.add(i,last,-1);
bit.add(nex[i],last,1);
nex[last]=nex[i];
}
bit.add(nex[i],i,-1);
if(j){
bit.add(nex[j],i,1);
bit.add(nex[j],j,-1);
bit.add(i,j,1);
nex[i]=nex[j];
nex[j]=i;
}
else {
bit.add(fir[d],i,1);
nex[i]=fir[d],fir[d]=i;
}
tr.del(root[a[i]],i),tr.insert(root[d],i);
a[i]=d;
}
/*==================End====================*/
/*=========================================*/
/*==============线段树套线段树===============*/
#define ls(x) x<<1
#define rs(x) x<<1|1
struct Next_Segment_Tree{
int root[maxn<<2];
void add(int poi,int l,int r,int node,int pl,int d){
dst.add(pl,1,n,root[node],d);
if(l==r)return;
int mid=l+r>>1;
if(poi<=mid)add(poi,l,mid,ls(node),pl,d);
else add(poi,mid+1,r,rs(node),pl,d);
}
int ask(int L,int l,int r,int node,int ll,int rr){
if(L<=l)return dst.ask(ll,rr,1,n,root[node]);
int mid=l+r>>1;
return (L<=mid?ask(L,l,mid,ls(node),ll,rr):0)+ask(L,mid+1,r,rs(node),ll,rr);
}
}nst;
int root[1000005],fir[1000005],nex[maxn],pre[1000005],a[maxn];
inline void change(int i,int d){
if(a[i]==d)return;
int last=tr.getpre(root[a[i]],i),j=tr.getpre(root[d],i);
if(fir[a[i]]==i)fir[a[i]]=nex[i];
if(last){
nst.add(i,1,n+1,1,last,-1);
nst.add(nex[i],1,n+1,1,last,1);
nex[last]=nex[i];
}
nst.add(nex[i],1,n+1,1,i,-1);
if(j){
nst.add(nex[j],1,n+1,1,i,1);
nst.add(nex[j],1,n+1,1,j,-1);
nst.add(i,1,n+1,1,j,1);
nex[i]=nex[j];
nex[j]=i;
}
else {
nst.add(fir[d],1,n+1,1,i,1);
nex[i]=fir[d],fir[d]=i;
}
tr.del(root[a[i]],i),tr.insert(root[d],i);
a[i]=d;
}
/*==============End===============*/
int main(){
n=read();
int m=read();
for(register int i=1;i<=n;++i){
a[i]=read(),nex[pre[a[i]]]=i,pre[a[i]]=i;
if(!fir[a[i]])fir[a[i]]=i;
tr.insert(root[a[i]],i);
}
for(register int i=1;i<=n;++i){
if(!nex[i])nex[i]=n+1;
bit.add(nex[i],i,1);
}
for(register int i=1;i<=1000000;++i)
if(!fir[i])fir[i]=n+1;
char s[2];
int l,r;
while(m--){
scanf("%s",s);
if(s[0]=='Q')l=read(),r=read(),printf("%d\n",bit.ask(n+1,l,r)-bit.ask(r,l,r));
else l=read(),r=read(),change(l,r);
}
}
