只对的后面3个点，做法是三维偏序，求大佬给一个hack

#include<bits/stdc++.h>
#define N 1123456
#define inf 10000010
#define lowbit(x) ((-x)&(x))
using namespace std ;
int n , q , front[N] , tr[N] , yuan[N] , cnt=0 , num , ans[N] ;
set<int> col[N] ;
struct node{
	int opt , x , k , l , r , i ;
}a[N<<2],q1[N<<2],q2[N<<2];
void change(int x,int k){
	while(x<=n){
		tr[x] += k ;
		x += lowbit(x) ;
	}
}
int ask(int x){
	int ans=0 ;
	while(x){
		ans += tr[x] ;
		x -= lowbit(x) ;
	}
	return ans ;
}
void solve(int l,int r,int L,int R){
	if(l>r||L>R) return ;
	int mid=(l+r)>>1 , tot1=0 , tot2=0 ; 
	for(int i=L;i<=R;i++){
		if(a[i].opt==1){
			if(a[i].x<=mid) change(a[i].i,a[i].k) , q1[++tot1] = a[i] ;
			else q2[++tot2] = a[i] ;
		}else{
			if(a[i].l<=mid) q1[++tot1] = a[i] ;
			else{
				int x=ask(a[i].r)-ask(a[i].l-1) ;
				ans[a[i].i] += x ;
				q2[++tot2] = a[i] ;
			}
		}
	}
	for(int i=1;i<=tot1;i++){
		a[i+L-1] = q1[i] ;
		if(q1[i].opt==1) change(q1[i].i,-q1[i].k) ;
	}
	for(int i=1;i<=tot2;i++) a[i+L-1+tot1] = q2[i] ;
	if(l!=r) solve(l,mid,L,L+tot1-1) ;
	solve(mid+1,r,L+tot1,R) ;
}
int read(){
	int x=0 ;
	char a=getchar() ;
	while(!(a>='0'&&a<='9')){
		a = getchar() ;
	}
	while(a>='0'&&a<='9'){
		x *= 10 ;
		x += a-'0' ;
		a = getchar() ;
	}
	return x ;
}
void write(int x){
	if(x>9) write(x/10) ;
	putchar(x%10+'0') ;
}
signed main(){
	cin >> n >> q ;
	for(int i=1;i<=n;i++){
		yuan[i] = read() ;
		if(col[yuan[i]].empty()) front[i]=0 , col[yuan[i]].insert(inf) , col[yuan[i]].insert(0) ;
		else{
			set<int>::iterator it=col[yuan[i]].lower_bound(i) ;
			it-- ;
			front[i] = *it ;
		}
		col[yuan[i]].insert(i) ;
		a[i].opt = 1 , a[i].i = i , a[i].k = 1 , a[i].x = front[i] ;
	}
	cnt = n ;
	for(int i=1;i<=q;i++){
		char opt ;
		int x , y ;
		cin >> opt ;
		x = read() , y = read() ;
		if(opt=='Q'){
			cnt++ ;
			a[cnt].opt = 2 , a[cnt].i = ++num , a[cnt].l = x , a[cnt].r = y;
		}else{
			cnt++ ;
			a[cnt].opt = 1 , a[cnt].x = front[x] , a[cnt].i = x , a[cnt].k = -1 ;
			set<int>::iterator it=col[yuan[x]].upper_bound(x) ;
			if(*it!=inf) front[*it] = front[x] ;
			col[yuan[x]].erase(x) ;
			yuan[x] = y ;
			if(col[yuan[x]].empty()) col[yuan[x]].insert(inf) , col[yuan[x]].insert(0) ;
			it = col[yuan[x]].upper_bound(x) ;
			if(*it!=inf){
				cnt++ ;
				a[cnt].opt = 1 , a[cnt].x = front[*it] , a[cnt].i = *it , a[cnt].k = -1 ;
				front[*it] = x ;
				cnt++ ;
				a[cnt].opt = 1 , a[cnt].x = front[*it] , a[cnt].i = *it , a[cnt].k = 1 ;
			}
			it-- ;
			front[x] = *it ;
			col[yuan[x]].insert(x) ;
			cnt++ ;
			a[cnt].opt = 1 , a[cnt].x = front[x] , a[cnt].i = x , a[cnt].k = 1 ;
		}
	}
	solve(0,n,1,cnt) ;
	for(int i=1;i<=num;i++) write(ans[i]) , putchar('\n') ;
	return 0 ;
}