洛谷P1903 [国家集训队]数颜色 / 维护队列

带修莫队板子，加上修改操作以后多了一个时间戳作为询问的第三维限制，记块大小为$B$，考虑以前两维块编号为第一二关键字，最后一维为第三关键字排序，那么前两维指针移动次数为$nB$，最后一维指针移动次数为$\displaystyle n\times \left(\frac{n}{B}\right)^2 = \frac{n^3}{B^2}$，于是取$B=n^{2/3}$时最优，复杂度为$O(n^{5/3})$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct QRY{int l, r, time, id;}qry[N];

struct MDF{int x, t;}mdf[N];

int n, m, col[N];

int l[N], r[N], bel[N], cnt[N], ans[N];

bool cmp(QRY a, QRY b) {
    return bel[a.l] == bel[b.l] ? bel[a.r] == bel[b.r] ? a.time < b.time : bel[a.r] < bel[b.r] : bel[a.l] < bel[b.l];
}

bool add(int x) {return !cnt[col[x]]++;}

bool del(int x) {return !--cnt[col[x]];}

int go(int x, int now) {
    int res = 0;
    if (qry[x].l <= mdf[now].x && mdf[now].x <= qry[x].r) {
        res = -!--cnt[col[mdf[now].x]] + !cnt[mdf[now].t]++;
    }
    swap(col[mdf[now].x], mdf[now].t); return res;
}

int main() {
    n = read(); m = read();
    for (int i = 1; i <= n; i++) col[i] = read();
    int S = pow(n, 2.0 / 3.0), k = 0;
    for (int i = 1; i <= n; i += S) {
        l[++k] = i; r[k] = i + S - 1;
    }
    for (int i = 1; i <= k; i++) {
        for (int j = l[i]; j <= r[i]; j++) bel[j] = i;
    }
    int t1 = 0, t2 = 0;
    for (int i = 1; i <= m; i++) {
        char opt[2]; scanf("%s", opt);
        if (opt[0] == 'Q') qry[++t1] = (QRY){read(), read(), t2, t1};
        if (opt[0] == 'R') mdf[++t2] = (MDF){read(), read()};
    }
    sort(qry + 1, qry + t1 + 1, cmp);
    int l = 1, r = 0, now = 0, res = 0;
    for (int i = 1; i <= t1; i++) {
        while (l < qry[i].l) res -= del(l++);
        while (l > qry[i].l) res += add(--l);
        while (r < qry[i].r) res += add(++r);
        while (r > qry[i].r) res -= del(r--);
        while (now < qry[i].time) res += go(i, ++now);
        while (now > qry[i].time) res += go(i, now--);
        ans[qry[i].id] = res;
    }
    for (int i = 1; i <= t1; i++) printf("%d\n", ans[i]);
    return 0;
}