【题目描述】
给定颜色序列,每次询问某个区间 $[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("%dn", ans[i]); return 0; }就是这样咯~
近期评论