P1903「[国家集训队]数颜色」

6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

4
4
3
4

#include<bits/stdc++.h>
using namespace std;

#ifndef _MOBK_
#define _MOBK_
#define ll long long
#define il inline
#define re register
#define MAXN 2000100

char buf[200];

il ll read_number() {
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

il ll read_capital() {
    char ch = getchar();
    while(ch < 'A' || ch > 'Z'){
        ch = getchar();
    }
    return ch;
}

il void write(ll x) {
    ll cnt = 0;
    while(x || !cnt) {
        buf[cnt++] = (x%10) + 48;
        x /= 10;
    }
    while(cnt) {
        putchar(buf[--cnt]);
    }
    putchar('\n');
}

// 分块大小
ll bz;
// 莫队
struct MOBK {
    // 查询区间
    struct Query {
        ll l, r, t, idx;
        bool operator < (const Query q) const {
            return l/bz != q.l/bz ? l < q.l : 
                r/bz != q.r/bz ? r < q.r : t < q.t;
                // (r/bz) & 1 ? t < q.t : t > q.t;
        }
    };
    // 修改记录
    struct Record {
        ll p, v;            // 下标，值
    };
    ll n, m, k;             // 数列长度，查询次数，修改次数
    ll curans;              // 当前查询答案
    ll count[MAXN];         // 计数数组
    ll result[MAXN];        // 答案数组（具体问题具体分析）
    Record modify[MAXN];    // 修改数组
    Query query[MAXN];      // 查询区间数组
    // 初始化
    MOBK() {
        curans = 0;
        memset(count, 0, sizeof(count));
    }
    MOBK(ll _n): n(_n) {
        bz = (ll)pow(n, 2.0/3);
        curans = 0;
        memset(count, 0, sizeof(count));
    }
    // 区间长度增一
    il void add(ll x) {
        curans += count[x] == 0 ? 1 : 0;
        ++count[x];
    }
    // 区间长度减一
    il void del(ll x) {
        --count[x];
        curans -= count[x] == 0 ? 1 : 0;
        
    }
    // 求解答案
    void solver(ll *a) {
        sort(query, query+m);
        re ll l = query[0].l;
        re ll r = query[0].l-1;
        re ll t = 0;
        for(re ll i = 0; i < m; ++i) {
            // printf("(%d,%d,%d)\n", query[i].l, query[i].r, query[i].t);
            while(l < query[i].l) {
                del(a[l++]);
            }
            while(l > query[i].l) {
                add(a[--l]);
            }
            while(r < query[i].r) {
                add(a[++r]);
            }
            while(r > query[i].r) {
                del(a[r--]);
            }
            while(t < query[i].t) {
                if(l <= modify[t].p && modify[t].p <= r) {
                    del(a[modify[t].p]);
                    add(modify[t].v);
                }
                swap(a[modify[t].p], modify[t].v);
                ++t;
            }
            while(t > query[i].t) {
                --t;
                if(l <= modify[t].p && modify[t].p <= r) {
                    del(a[modify[t].p]);
                    add(modify[t].v);
                }
                swap(a[modify[t].p], modify[t].v);
            }
            result[query[i].idx] = curans;
        }
        for(ll i = 0; i < m; ++i) {
            // write(result[i]);
            printf("%lld\n", result[i]);
        }
    }
};
#endif

int main()
{
    char option;
    ll q = 0, r = 0;
    ll n = read_number();
    ll m = read_number();
    static ll a[MAXN] = {0};
    static MOBK mobk = MOBK(n);
    for(re ll i = 0; i < n; ++i) {
        a[i] = read_number();
    }
    for(re ll i = 0; i < m; ++i) {
        option = read_capital();
        if(option == 'Q') {
            mobk.query[q].l = read_number() - 1;
            mobk.query[q].r = read_number() - 1;
            mobk.query[q].t = r;
            mobk.query[q].idx = q;
            ++q;
        } else {
            mobk.modify[r].p = read_number() - 1;
            mobk.modify[r].v = read_number();
            ++r;
        }
    }
    mobk.m = q;
    mobk.k = r;
    mobk.solver(a);
    return 0;
}