rt，AC on 11~13

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int COL = 1e6 + 10;
int n, q, k;
int cntq, cntr;
int a[N];
struct stu
{
    int l, r;
    int id, time;
}ask[N];
struct node
{
    int pos, col;
}upt[N];
int l, r, t, now;
int cnt[COL], ans[N];

bool cmp(stu a1, stu a2)
{
    return a1.l / k ^ a2.l / k ? a1.l < a2.l : (a1.r / k ^ a2.r / k ? a1.r < a2.r :a1.time < a2.time);
}

void add(int x)
{
    if(!cnt[x]) now++;
    cnt[x]++;
}

void del(int x)
{
    cnt[x]--;
    if(!cnt[x]) now--;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    k = pow(n, 2 / 1.0 / 3);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= q; i++)
    {
        char op;
        cin >> op;
        if(op == 'Q')
        {
            cntq++;
            cin >> ask[cntq].l >> ask[cntq].r;
            ask[cntq].id = cntq;
            ask[cntq].time = cntr;
        }
        else 
        {
            cntr++;
            cin >> upt[cntr].pos >> upt[cntr].col;
        }
    }
    sort(ask + 1, ask + cntq + 1, cmp);
    for(int i = 1; i <= cntq; i++)
    {
        while(l > ask[i].l) add(a[--l]);
        while(r < ask[i].r) add(a[++r]);
        while(l < ask[i].l) del(a[l++]);
        while(r > ask[i].r) del(a[r--]);
        while(t < ask[i].time)
        {
            t++;
            if(ask[i].l <= upt[t].pos && upt[t].pos <= ask[i].r) {del(a[upt[cntr].pos]), add(upt[t].col);}
            swap(a[upt[t].pos], upt[t].col);
        }
        while(t > ask[i].time)
        {
            if(ask[i].l <= upt[t].pos && upt[t].pos <= ask[i].r) {del(a[upt[cntr].pos]), add(upt[t].col);}
            swap(a[upt[t].pos], upt[t].col);
            t--;
        }      
        ans[ask[i].id] = now; 
    }
    for(int i = 1; i <= cntq; i++) cout << ans[i] << "\n";
    return 0;
}