RT，写的树套树两个log但是常数较大。

#include <bits/stdc++.h>
using namespace std;
namespace io {
	const int __SIZE = (2e7) + 1;
	char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1, __c, qu[55]; int __f, qr, _eof;
	#define Gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, __SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
	inline void flush () { fwrite (obuf, 1, oS - obuf, stdout), oS = obuf; }
	inline void gc (char &x) { x = Gc(); }
	inline void pc (char x) { *oS ++ = x; if (oS == oT) flush (); }
	inline void pstr (const char *s) { int __len = strlen(s); for (__f = 0; __f < __len; ++__f) pc (s[__f]); }
	inline void gstr (char *s) { for(__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)  __c = Gc();
		for(; __c > 31 && __c < 127 && __c != ' ' && __c != '\n' && __c != '\r'; ++s, __c = Gc()) *s = __c; *s = 0; }
	template <class I> inline bool gi (I &x) { _eof = 0;
		for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) { if (__c == '-') __f = -1; _eof |= __c == EOF; }
		for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc()) x = x * 10 + (__c & 15), _eof |= __c == EOF; x *= __f; return !_eof; }
	template <class I> inline void print (I x) { if (!x) pc ('0'); if (x < 0) pc ('-'), x = -x;
		while (x) qu[++ qr] = x % 10 + '0',  x /= 10; while (qr) pc (qu[qr --]); }
	struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
} using io::pc; using io::gc; using io::pstr; using io::gstr; using io::gi; using io::print;
const int N = 200010, Log = 20;
int n, m, a[N], pre[N];
int lst[1000100],rt[N];
set<int> st[1000100];
int rd[N*Log], ls[N*Log], rs[N*Log], val[N*Log], cnt = 0;
unsigned sz[N*Log];
unsigned gen() {
	static unsigned x = 2333;
	x ^= x<<13;
	x ^= x>>7;
	x ^= x<<17;
	return x; 
}
inline int nw(int x) {
	val[++cnt] = x;
	rd[cnt] = gen();
	sz[cnt] = 1;
	return cnt;
}
inline void pu(int p){sz[p]=sz[ls[p]]+sz[rs[p]]+1;}
inline void split(int p,int& l,int& r,int v){
	if (!p) return (void)(l=r=0);
	if(val[p]<=v) l=p,split(rs[p],rs[l],r,v),pu(l);
	else r=p,split(ls[p],l,ls[r],v),pu(r);
}
inline void merge(int& p,int l, int r) {
	if(!l||!r) return (void)(p=l+r);
	if(rd[l]<rd[r]) p=l,merge(rs[p],rs[l],r);
	else p=r,merge(ls[p],l,ls[r]); pu(p);
}
inline void ins(int&r, int v){
	int a=0,b=0;
	split(r,a,b,v);
	merge(a,a,nw(v));
	merge(r,a,b);
}
inline void del(int&r, int v){
	int a=0,b=0,c=0;
	split(r,a,b,v);
	split(a,a,c,v-1);
	merge(c,ls[c],rs[c]);
	merge(a,a,c),merge(r,a,b);
}
inline int qans(int&r, int L,int R){
	int a=0,b=0,c=0;
	split(r,a,b,R),split(a,a,c,L-1);
	int ans=sz[c];
	merge(a,a,c),merge(r,a,b);return ans;
}
inline void add(int x, int v) {
	for (; x <= n; x += x & -x) ins(rt[x], v);
}
inline void sub(int x, int v) {
	for(; x <= n; x += x & -x) del(rt[x], v);
}
inline int qry(int x, int lv, int rv) {
	int ans = 0;
	for (; x; x -= x & -x) ans += qans(rt[x], lv, rv);
	return ans;
}
inline int qry(int l, int r, int lv, int rv) {
	return qry(r, lv, rv) - qry(l-1, lv, rv);
}
inline void era(int x, int p) {
	set<int>::iterator it = st[x].lower_bound(p);
	if((--st[x].end()) != it) {
		int nex = *(++it);--it;
		int ft = 0;
		if(it != st[x].begin()) ft = *(--it),++it;
		sub(nex, pre[nex]);  pre[nex] = ft; add(nex, pre[nex]);
	}
	sub(p,pre[p]); st[x].erase(it);
}
inline void are(int x, int p) {
//	cerr<<"???\n";
	set<int>::iterator it = st[x].lower_bound(p);
	int pr = 0;
	if (it != st[x].begin()) pr = *(--it),++it;
	pre[p] = pr; add(p, pre[p]);
	if((st[x].end()) != it) {
		int nex = *(it);
		sub(nex,pre[nex]);pre[nex]=p;add(nex,pre[nex]);
	}
	st[x].insert(p);
}
int main() {
//	freopen("fff.txt","r",stdin);
//	freopen("fff.out","w",stdout);
//	gi(n),gi(m);
	gi(n),gi(m);
	for (int i = 1; i <= n; ++i) gi(a[i]),pre[i] = lst[a[i]], lst[a[i]] = i, st[a[i]].insert(i), add(i, pre[i]);
	while (m--) {
		char op[3];gstr(op);
		if (op[0] == 'Q') {
			int l,r; gi(l),gi(r);
		//	scanf("%d%d",&l,&r);
			print(qry(l, r, 0, l-1)),pc('\n');
		} else if(op[0]=='R') {
			int p,col;gi(p),gi(col);
		//	scanf("%d%d",&p,&col);
			era(a[p], p);
			a[p] = col;
			are(a[p], p);
		}
	//	for (int i = 1; i <= n; ++i) {
	//	cout << pre[i] << " ";
	//}cout << endl;
	}
	return 0;
}