RT，楼主太菜了，倒数第二和第三个点每次都是2.7s卡不过去啊！！块长$n^{\frac{2}{3}}$和$n^{\frac{3}{4}}$都试过了，O2也开了，快度快写也加了，就是卡不过去QwQ （而且不知道为什么最后一个点还WA了）

求大佬帮忙！谢谢！

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define rep(i, m, n) for(int i = m; i <= n; i++)
#define per(i, m, n) for(int i = m; i >= n; i--)

template<class Ty> 
inline void read(Ty & X) {
    X = 0; Ty flag = 1; char ch = getchar();
    while(ch < '0' || ch > '9') { if (ch == '-') flag = 0; ch = getchar(); }
    while(ch >= '0' && ch <= '9') { X = (X << 1) + (X << 3) + ch - '0'; ch = getchar(); }
    if (!flag) X = ~(X - 1);
}

template<class Ty> 
inline void write(Ty X) {
    if (X < 0) { X = ~(X - 1); putchar('-'); }
    if (X > 9) write(X / 10);
    putchar(X % 10 + '0');
}

const int maxn = 133340;
const int maxc = 1e6 + 5;

int ans[maxn], a[maxn], belong[maxn], cnt[maxc];

struct query {
	int l, r, t, id;
} q[maxn]; 

struct update {
	int pos, color, last;
} c[maxn];

int cmp(query &a, query &b) {
	return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.r] ^ belong[b.r]) ? belong[a.r] < belong[b.r] : a.t < b.t);
}

int cntq, cntc, N, M; 

int main() {
    read(N), read(M);
    rep(i, 1, N) read(a[i]);
    rep(i, 1, M) {
    	char ch;
    	scanf("%c", &ch);
    	if (ch == 'Q') {
    		read(q[++cntq].l), read(q[cntq].r), q[cntq].t = cntc, q[cntq].id = cntq;
    	} else read(c[++cntc].pos), read(c[cntc].color);
    }
    int block = pow(N, 2.0 / 3.0);  
    int num = ceil((double) N / block);
    rep(i, 1, num) rep(j, (i - 1) * block + 1, min(i * block, N)) belong[j] = i;
    sort(q + 1, q + cntc + 1, cmp);
    int l = 1, r = 0, t = 0, now = 0;
    rep(i, 1, M) {
    	int ql = q[i].l, qr = q[i].r, qt = q[i].t;
    	while (l < ql) now -= !--cnt[a[l++]];
    	while (l > ql) now += !cnt[a[--l]]++;
    	while (r < qr) now += !cnt[a[++r]]++;
    	while (r > qr) now -= !--cnt[a[r--]];
    	while (t < qt) {
    		++t;
    		if (ql <= c[t].pos && c[t].pos <= qr) now -= !--cnt[a[c[t].pos]] - !cnt[c[t].color]++;
    		swap(a[c[t].pos], c[t].color);
    	}
    	while (t > qt) {
    		if (ql <= c[t].pos && c[t].pos <= qr) now -= !--cnt[a[c[t].pos]] - !cnt[c[t].color]++;
    		swap(a[c[t].pos], c[t].color);
    		--t;
    	}
    	/*
    	while (t != qt) {
    		if (t < qt) ++t;
    		if (ql <= c[t].pos && c[t].pos <= qr) now -= !--cnt[a[c[t].pos]] - !cnt[c[t].color]++;
    		swap(a[c[t].pos], c[t].color);
    		if (t > qt) --t;    		
    	}
    	*/
    	ans[q[i].id] = now;
    }
    rep(i, 1, cntq) write(ans[i]), puts("");
    return 0; 
}