带修莫队板子求调玄关

#include <cstdio>
#include <cmath>
#include <algorithm>
#define bel(x) ((x - 1) / SIZE + 1)
const int N = 2e5 + 5;
int n, m, a[N];
struct Query { int l, r, t, idx; } q[N];
int totq;
struct Replace { int p, c; } c[N];
int totc;
int SIZE;
int cnt[N], cur = 0, ans[N];
void add(const int &p) {
    if (!cnt[p]++) cur++;
}
void del(const int &p) {
    if (!--cnt[p]) cur--;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", a + i);
    SIZE = pow(n, 2.0 / 3);
    for (int i = 1; i <= m; i++) {
        char s; int x, y;
        scanf(" %c %d %d", &s, &x, &y);
        if (s == 'Q') q[++totq] = { x, y, totc, totq };
        else c[++totc] = { x, y };
    }
    auto comp = [](const Query &x, const Query &y) {
        if (bel(x.l) != bel(y.l))
            return bel(x.l) < bel(y.l);
        if (bel(x.r) != bel(y.r))
            return bel(x.r) < bel(y.r);
        return x.t < y.t;
    };
    std::sort(q + 1, q + totq + 1, comp);
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= totq; i++) {
        while (r < q[i].r)
            add(a[++r]);
        while (r > q[i].r)
            del(a[r--]);
        while (l > q[i].l)
            add(a[--l]);
        while (l < q[i].l)
            del(a[l++]);
        while (t < q[i].t) {
            t++;
            if (l <= c[t].p && c[t].p <= r) {
                add(c[t].c);
                del(a[c[t].p]);
            }
            std::swap(a[c[t].p], c[t].c);
        }
        while (t > q[i].t) {
            if (l <= c[t].p && c[t].p <= r) {
                add(c[t].c);
                del(a[c[t].p]);
            }
            std::swap(a[c[t].p], c[t].c);
            t--;
        }
        ans[q[i].idx] = cur;
    }
    for (int i = 1; i <= totq; i++)
        printf("%d\n", ans[i]);
    return 0;
}