题目链接：BZOJ 2120

墨墨购买了一套 $n​$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

• Q l r：询问从第 $l$ 支画笔到第 $r$ 支画笔中共有几种不同颜色的画笔。
• R p c ：把第 $p$ 支画笔替换为颜色 $c$。

数据范围：$1\le n,m\le 5\times 10^4$，$1\le c\le 10^6​$。

Solution

由于没有区间可加性，我们考虑带修改莫队。根据「算法笔记」带修改莫队算法 中的分析，我们直接 $n^{\frac{2}{3}}$ 分块，然后把询问离线下来，按照套路直接做就行了。

据说这题分块 + $\text{bitset}​$ 可以卡过去？但是我卡了一个晚上常数还是只有 $80​$ 分啊 QAQ

时间复杂度：$\mathcal O(n^\frac{5}{3})$。

Code

分块

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>

const int N = 1e5 + 5, M = 230;

int n, m, len, num, a[N], v[N], p[N][3], bl[N], l[M], r[M], cnt[M][N];
std::bitset<N> f[M];

void read(int &t) {
    t = 0;
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; c >= '0' && c <= '9'; t = t * 10 + (c ^ 48), c = getchar());
}
void print(int x) {
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
char getc() {
    char c = getchar();
    while (c != 'Q' && c != 'R') c = getchar();
    return c;
}
void build() {
    len = sqrt(n), num = (n - 1) / len + 1;
    for (int i = 1; i <= n; i++) {
        bl[i] = (i - 1) / len + 1;
        if (++cnt[bl[i]][a[i]] == 1) f[bl[i]][a[i]] = 1;
    }
    for (int i = 1; i <= num; i++) {
        l[i] = (i - 1) * len + 1, r[i] = i * len;
    }
    r[num] = n;
}
void modify(int x, int c) {
    if (--cnt[bl[x]][a[x]] == 0) f[bl[x]][a[x]] = 0;
    a[x] = c;
    if (++cnt[bl[x]][a[x]] == 1) f[bl[x]][a[x]] = 1;
}
int query(int x, int y) {
    std::bitset<N> ans;
    if (bl[x] == bl[y]) {
        for (int i = x; i <= y; i++) ans[a[i]] = 1;
    } else {
        for (int i = bl[x] + 1; i <= bl[y] - 1; i++) ans |= f[i];
        for (int i = x; i <= r[bl[x]]; i++) ans[a[i]] = 1;
        for (int i = l[bl[y]]; i <= y; i++) ans[a[i]] = 1;
    }
    return ans.count();
}
int main() {
    read(n), read(m);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        read(a[i]), v[++tot] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        p[i][0] = (getc() == 'R');
        read(p[i][1]), read(p[i][2]);
        if (p[i][0]) v[++tot] = p[i][2];
    }
    std::sort(v + 1, v + tot + 1);
    tot = std::unique(v + 1, v + tot + 1) - (v + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(v + 1, v + tot + 1, a[i]) - v;
    }
    for (int i = 1; i <= m; i++) {
        if (p[i][0]) p[i][2] = std::lower_bound(v + 1, v + tot + 1, p[i][2]) - v;
    }
    build();
    for (int i = 1; i <= m; i++) {
        if (p[i][0]) {
            modify(p[i][1], p[i][2]);
        } else {
            print(query(p[i][1], p[i][2])), puts("");
        }
    }
    return 0;
}

莫队

#include <cstdio>
#include <cmath>
#include <algorithm>

const int N = 5e4 + 5, M = 1e6 + 5;

int n, m, cnt1, cnt2, ret, a[N], b[N], bl[N], cnt[M], ans[N];

struct Data1 {
    int l, r, t, id;
    Data1(int _l = 0, int _r = 0, int _t = 0, int _id = 0) {
        l = _l, r = _r, t = _t, id = _id;
    }
    bool operator<(const Data1 &b) const {
        return bl[l] == bl[b.l] ? bl[r] == bl[b.r] ? t < b.t : r < b.r : l < b.l;
    }
} q[N];

struct Data2 {
    int x, u, v;
    Data2(int _x = 0, int _u = 0, int _v = 0) {
        x = _x, u = _u, v = _v;
    }
} r[N];

void add(int c) {
    if (++cnt[c] == 1) ret++;
}
void del(int c) {
    if (--cnt[c] == 0) ret--;
}
void modify(int l, int r, int x, int c) {
    if (l <= x && x <= r) del(a[x]), add(c);
    a[x] = c;
}
int main() {
    scanf("%d%d", &n, &m);
    int len = pow(n, 2.0 / 3);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]), b[i] = a[i];
        bl[i] = (i - 1) / len + 1;
    }
    for (int i = 1; i <= m; i++) {
        char s[5];
        int x, y;
        scanf("%s%d%d", s + 1, &x, &y);
        if (s[1] == 'Q') {
            cnt1++, q[cnt1] = Data1(x, y, cnt2, cnt1);
        } else {
            cnt2++, r[cnt2] = Data2(x, b[x], y), b[x] = y;
        }
    }
    std::sort(q + 1, q + cnt1 + 1);
    for (int L = 1, R = 0, T = 0, i = 1; i <= cnt1; i++) {
        int l = q[i].l, r = q[i].r, t = q[i].t;
        while (T < t) T++, modify(L, R, r[T].x, r[T].v);
        while (T > t) modify(L, R, r[T].x, r[T].u), T--;
        while (L < l) del(a[L++]);
        while (L > l) add(a[--L]);
        while (R < r) add(a[++R]);
        while (R > r) del(a[R--]);
        ans[q[i].id] = ret;
    }
    for (int i = 1; i <= cnt1; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}