「BZOJ 2120」数颜色 - 带修改莫队

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

Q L R 代表询问你从第支画笔到第支画笔中共有几种不同颜色的画笔。
R P Col 把第支画笔替换为颜色。

为了满足墨墨的要求，你知道你需要干什么了吗？

链接

BZOJ 2120

题解

为每个修改操作分配一个时刻，为每个查询记录其时刻，即受到了前多少次修改的影响。

将序列分块，每块，将询问排序，左端点所在块为第一关键字，右端点所在块为第二关键字，查询时刻为第三关键字，莫队转移即可。

注意需要记录每次修改的旧值，以便撤销。

代码

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

const int MAXN = 10000;
const int MAXM = 10000;
const int MAXX = 1e6;

int n, a[MAXN + 1], blockSize;

struct Update {
    int pos, oldVal, newVal;
} b[MAXM + 1];

int q, ans[MAXM + 1], cnt[MAXX + 1];

struct Query {
    int id, l, r, time, block;

    bool operator<(const Query &other) const {
        if (l / blockSize == other.l / blockSize) {
            if (r / blockSize == other.r / blockSize) {
                return time < other.time;
            } else return r / blockSize < other.r / blockSize;
        } else return l / blockSize < other.l / blockSize;
    }
} Q[MAXM + 1];

inline int extend(int l, int r, bool left, int d) {
    if (left) {
        if (d == 1) {
            if (++cnt[a[l]] == 1) return 1;
            else return 0;
        } else {
            if (--cnt[a[l]] == 0) return -1;
            else return 0;
        }
    } else {
        if (d == 1) {
            if (++cnt[a[r]] == 1) return 1;
            else return 0;
        } else {
            if (--cnt[a[r]] == 0) return -1;
            else return 0;
        }
    }
}

inline int update(int l, int r, int time, int d) {
    Update x = b[time];
    int res = 0;
    if (d == 1) {
        a[x.pos] = x.newVal;
        if (x.pos >= l && x.pos <= r) {
            if (--cnt[x.oldVal] == 0) res--;
            if (++cnt[x.newVal] == 1) res++;
        }
    } else {
        if (x.pos >= l && x.pos <= r) {
            if (--cnt[x.newVal] == 0) res--;
            if (++cnt[x.oldVal] == 1) res++;
        }
        a[x.pos] = x.oldVal;
    }
    return res;
}

inline void prepare(int t) {
    static int newA[MAXN + 1];
    std::copy(a + 1, a + n + 1, newA + 1);
    for (int i = 1; i <= t; i++) {
        b[i].oldVal = newA[b[i].pos];
        newA[b[i].pos] = b[i].newVal;
    }
}

inline void solve() {
    int l = 1, r = 0, time = 0, ans = 0;
    for (int i = 1; i <= q; i++) {
        while (r < Q[i].r) ans += extend(l, ++r, false, 1);
        while (r > Q[i].r) ans += extend(l, r--, false, -1);

        while (l > Q[i].l) ans += extend(--l, r, true, 1);
        while (l < Q[i].l) ans += extend(l++, r, true, -1);

        while (time < Q[i].time) ans += update(l, r, ++time, 1);
        while (time > Q[i].time) ans += update(l, r, time--, -1);

        ::ans[Q[i].id] = ans;
    }
}

int main() {
    int m, t = 0;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    for (int i = 1; i <= m; i++) {
        char cmd[2];
        scanf("%s", cmd);
        if (cmd[0] == 'Q') {
            q++;
            Q[q].id = q;
            scanf("%d %d", &Q[q].l, &Q[q].r);
            Q[q].time = t;
        } else {
            t++;
            scanf("%d %d", &b[t].pos, &b[t].newVal);
        }
    }

    prepare(t);

    blockSize = floor(pow(n, 2.0 / 3) + 1);
    std::sort(Q + 1, Q + q + 1);

    solve();

    for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);

    return 0;
}