树状数组套线段树，牛客和acwing上可过，但是在洛谷上WA on 1~10

#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define ls(u) tr[u].son[0]
#define rs(u) tr[u].son[1]
const int N=133331+10,M=1e6+10;
const int INF=0x3f3f3f3f;
int n,m,lst[N];
set<int> col[M];
inline int pre(int id,int val){
    if(col[id].empty())return 0;
    auto it=col[id].lower_bound(val);
    it--;
    if(*it>=val)return 0;
    return *it;
}
inline int suc(int id,int val){
    auto it=col[id].upper_bound(val);
    if(it==col[id].end())return INF;
    return *it;
}
int rt[N],idx,v[N];
struct Node{
    int son[2];
    int cnt;
}tr[10*M];
inline void insert(int& u,int l,int r,int x){
    if(!u)u=++idx;
    tr[u].cnt++;
    if(l==r)return ;
    int mid=l+r>>1;
    if(x<=mid)insert(ls(u),l,mid,x);
    else insert(rs(u),mid+1,r,x);
}
inline void del(int& u,int l,int r,int x){
    tr[u].cnt--;
    if(l==r)return ;
    int mid=l+r>>1;
    if(x<=mid)del(ls(u),l,mid,x);
    else del(rs(u),mid+1,r,x);
}
inline void insert(int x){
    for(int i=x;i<=n;i+=i&-i)
        insert(rt[i],0,n,lst[x]);
}
inline void update(int x,int c){
    int last_l=pre(v[x],x),last_r=suc(v[x],x);
    int now_l=pre(c,x),now_r=suc(c,x);
    for(int i=x;i<=n;i+=i&-i)del(rt[i],0,n,last_l);
    if(last_r!=INF){
        lst[last_r]=last_l;
        for(int i=last_r;i<=n;i+=i&-i)del(rt[i],0,n,x),insert(rt[i],0,n,last_l);
    }
    if(now_r!=INF){
        lst[now_r]=x;
        for(int i=now_r;i<=n;i+=i&-i)del(rt[i],0,n,now_l),insert(rt[i],0,n,x);
    }
    for(int i=x;i<=n;i+=i&-i)insert(rt[i],0,n,now_l);
    col[v[x]].erase(x),col[c].insert(x);
    lst[x]=now_l,v[x]=c;
}
inline int query(vector<int>& q1,vector<int>& q2,int l,int r,int ql,int qr){
    if(ql>qr)return 0;
    if(l>=ql&&r<=qr){
        int res=0;
        for(auto u:q1)res+=tr[u].cnt;
        for(auto u:q2)res-=tr[u].cnt;
        return res;
    }
    else {
        int mid=l+r>>1,res=0;
        if(qr<=mid){
            for(auto& u:q1)u=ls(u);
            for(auto& u:q2)u=ls(u);
            res=query(q1,q2,l,mid,ql,qr);
        }
        else if(ql>mid){
            for(auto& u:q1)u=rs(u);
            for(auto& u:q2)u=rs(u);
            res=query(q1,q2,mid+1,r,ql,qr);
        }
        else {
            vector<int> nq1=q1,nq2=q2;
            for(auto& u:q1)u=ls(u);
            for(auto& u:q2)u=ls(u);
            for(auto& u:nq1)u=rs(u);
            for(auto& u:nq2)u=rs(u);
            res=query(q1,q2,l,mid,ql,qr)+query(nq1,nq2,mid+1,r,ql,qr);
        }
        return res;
    }
}
inline int query(int l,int r){
    vector<int> q1,q2;
    for(int i=r;i;i-=i&-i)q1.push_back(rt[i]);
    for(int i=l-1;i;i-=i&-i)q2.push_back(rt[i]);
    return query(q1,q2,0,n,0,l-1);
}
inline void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        lst[i]=pre(x,i),v[i]=x;
        col[x].insert(i);
        insert(i);
    }
    char opt[2];
    for(int i=0;i<m;i++){
        cin>>opt;
        if(opt[0]=='Q'){
            int l,r;
            cin>>l>>r;
            cout<<query(l,r)<<'\n';
        }
        else {
            int x,c;
            cin>>x>>c;
            update(x,c);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int testcase=1;
    while(testcase--)solve();
}