Hellc

【题目描述】

给定颜色序列，每次询问某个区间 $[l, r]$ 内，不同颜色的种数，要求支持单点修改颜色。

【题目链接】

BZOJ 2120 数颜色

【解题思路】

序列上带修改的莫队，详见 莫队算法 - 学习笔记

【AC代码】

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

const int MAXN = 10000;
const int MAXM = 10000;
const int MAXC = 1000000;

int n, m;
int qcnt, mcnt;
int color[MAXN];
int ans[MAXM];

struct Modification{
    int pos, color;
} modifications[MAXM];

int blockSize;

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

    inline friend bool operator<(const Query &a, const Query &b){
        if(a.l / blockSize != b.l / blockSize) return a.l / blockSize < b.l / blockSize;
        else if (a.r / blockSize != b.r / blockSize) return a.r / blockSize < b.r / blockSize;
        else return a.time < b.time;
    }
} querys[MAXM];

int l, r, currAns, currTime;
bool in[MAXN];
int buc[MAXC + 1];

void flip(int x){
    in[x] ^= 1;

    if(in[x]){
        if(++buc[ color[x] ] == 1) currAns++;
    } else{
        if(--buc[ color[x] ] == 0) currAns--;
    }
}

void flipModification(int x){
    Modification *o = modifications + x;

    if(l <= o->pos && o->pos <= r) flip(o->pos);
    std::swap(color[o->pos], o->color);
    if(l <= o->pos && o->pos <= r) flip(o->pos);
}

void solve(){
    blockSize = static_cast<int>(std::ceil(std::pow(n, 2.0 / 3.0)) + 1e-6);
    std::sort(querys, querys + qcnt);

    l = 0, r = 0, currTime = 0, flip(0);
    for(Query *q = querys; q != querys + qcnt; q++){
        while(currTime < q->time) flipModification(currTime++);
        while(currTime > q->time) flipModification(--currTime);

        while(l > q->l) flip(--l);
        while(r < q->r) flip(++r);
        while(l < q->l) flip(l++);
        while(r > q->r) flip(r--);

        ans[q->id] = currAns;
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++) scanf("%d", color + i);

    qcnt = 0, mcnt = 0;
    for(int i = 0; i < m; i++){
        char ch;
        do ch = getchar(); while(ch != 'Q' && ch != 'R');

        if(ch == 'Q'){
            Query *q = querys + qcnt;

            scanf("%d%d", &q->l, &q->r), q->l--, q->r--;
            q->id = qcnt, q->time = mcnt;

            qcnt++;
        } else{
            Modification *o = modifications + mcnt;

            scanf("%d%d", &o->pos, &o->color), o->pos--;

            mcnt++;
        }
    }

    solve();

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

    return 0;
}

就是这样咯~