题目大意：有$n$支画笔，有两个操作
- $Q\;l\;r：$询问$[l,r]$中有几种颜色
- $R\;p\;Col：$把第$p$支画笔的颜色改成$Col$
题解：带修莫队，分为$n^{\frac{1}{3}}$个块，每个块$n^{\frac{2}{3}}$个元素，复杂度$O(n^{\frac{5}{3}})$
卡点：读入时，修改的时间赋值错
C++ Code：#include#include #define maxn 50010#define bl(x) (x >> 10)int n, m, Qcnt, Mcnt;int C[maxn], ans[maxn], cnt[1000010];struct Query { int l, r, t, id; inline bool operator < (const Query &rhs) const { return bl(l) == bl(rhs.l) ? (bl(r) == bl(rhs.r) ? t < rhs.t : r < rhs.r) : l < rhs.l; }} Q[maxn];struct Modify { int pos, t, col;} M[maxn];int l = 0, r = 0, p = 0, res = 0;inline void swap(int &a, int &b) {a ^= b ^= a ^= b;}void modify(int x) { if (M[x].pos >= l && M[x].pos <= r) { res -= --cnt[C[M[x].pos]] == 0; res += cnt[M[x].col]++ == 0; } swap(M[x].col, C[M[x].pos]);}int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &C[i]); for (int i = 1; i <= m; i++) { char op[10]; scanf("%s", op); if (*op == 'Q') { Qcnt++; scanf("%d%d", &Q[Qcnt].l, &Q[Qcnt].r); Q[Qcnt].t = i; Q[Qcnt].id = Qcnt; } else { Mcnt++; scanf("%d%d", &M[Mcnt].pos, &M[Mcnt].col); M[Mcnt].t = i; } } std::sort(Q + 1, Q + Qcnt + 1); for (int i = 1; i <= Qcnt; i++) { while (l > Q[i].l) res += cnt[C[--l]]++ == 0; while (r < Q[i].r) res += cnt[C[++r]]++ == 0; while (l < Q[i].l) res -= --cnt[C[l++]] == 0; while (r > Q[i].r) res -= --cnt[C[r--]] == 0; while (p < Mcnt && M[p + 1].t <= Q[i].t) modify(++p); while (p && M[p].t > Q[i].t) modify(p--); ans[Q[i].id] = res; } for (int i = 1; i <= Qcnt; i++) printf("%d\n", ans[i]); return 0;}