#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

template<typename T> inline void read(T &x) {
   int s = 1, d = getchar(); x = 0;
   for ( ;!isdigit(d); d = getchar()) if (!(d^'-')) s = -1;
   while (isdigit(d)) x = x * 10 + (d&15), d = getchar();
   x *= s;
}
template<typename T, typename...L> inline void read(T &x, L &...l) { read(x), read(l...); }

template<class T> void write(T x) {
   if (x < 0) { putchar('-'); x = -x; }
   if (x > 9) write(x / 10); putchar(x % 10 + '0');
}
const int NN=1.5e5;
const int MM=1e6+10;
int N,M;
int a[NN],b[NN];
int blockSize;
int cnt[MM];
int colorType;

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

struct modify{
    int x,color;
}m[NN];
int modifyQwQ;

inline bool cmp(query x,query y){
    return b[x.l]^b[y.l]?b[x.l]<b[y.l]:x.r^y.r?b[y.l]&1?x.r<y.r:x.r>y.r:x.t<y.t;
}
//x.t^y.t?x.t<y.t:
int ans[NN];

int main(){
    freopen("test.in","r",stdin);
    read(N,M);
    blockSize=(int)pow(N,2.0/3);
    for(register int i=1;i<=N;++i){
        read(a[i]);
        b[i]=(i-1)/blockSize+1;
    }
    for(register int i=1;i<=M;i++){
        register char c;
        scanf("\n%c",&c);
        if(c^'Q'){
            modifyQwQ++;
            read(m[modifyQwQ].x,m[modifyQwQ].color);
        }else{
            queryQwQ++;
            read(q[queryQwQ].l,q[queryQwQ].r);
            q[queryQwQ].id=queryQwQ;
            q[queryQwQ].t=modifyQwQ;
        }
    }
    register int l=1,r=0,t=0;
    sort(q+1,q+1+queryQwQ,cmp);
    for(int i=1;i<=queryQwQ;i++){
        register int L=q[i].l,R=q[i].r,T=q[i].t;
        while(r<R) colorType+=!cnt[a[++r]]++^0;
        while(r>R) colorType-=!--cnt[a[r--]]^0;
        while(l<L) colorType-=!--cnt[a[l++]]^0;
        while(l>L) colorType+=!cnt[a[--l]]++^0;
        while(t<T){
            t++;
            if(l<=m[t].x&&m[t].x<=r) colorType-=!--cnt[a[m[t].x]]^0;
            swap(m[t].color,a[m[t].x]);
            if(l<=m[t].x&&m[t].x<=r) colorType+=!cnt[a[m[t].x]]++^0;
        }
        while(t>T){
            if(l<=m[t].x&&m[t].x<=r) colorType-=!--cnt[a[m[t].x]]^0;
            swap(m[t].color,a[m[t].x]);
            if(l<=m[t].x&&m[t].x<=r) colorType+=!cnt[a[m[t].x]]++^0;
            t--;
        }
        ans[q[i].id]=colorType;
    }
    for(int i=1;i<=queryQwQ;i++) write(ans[i]),puts("");
    return 0;
}

一直TLE #8、9、10三个点
但是也找不到什么可以优化的地方了
试过循环展开，但没什么效果qwq