[BZOJ 2120][国家集训队2011] 数颜色【带修改莫队】
Problem:
Description
墨墨购买了一套N支彩色画笔(其中有些颜色可能相同),摆成一排,你需要回答墨墨的提问。墨墨会像你发布如下指令: 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求,你知道你需要干什么了吗?
Input
第1行两个整数N,M,分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数,分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行,每行分别代表墨墨会做的一件事情,格式见题干部分。
Output
对于每一个Query的询问,你需要在对应的行中给出一个数字,代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
Sample Input
6 5 1 2 3 4 5 5 Q 1 4 Q 2 6 R 1 2 Q 1 4 Q 2 6
Sample Output
4 4 3 4
HINT
对于100%的数据,N≤10000,M≤10000,修改操作不多于1000次,所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
Source
国家集训队 2011
Solution:
带修改莫队大法好 !!!
在普通莫队的基础上,记录每个询问是在第几次修改之后,排序时作为第三关键字。
然后加一个指针 t 表示当前处于第几次修改之后,暴力移指针 l, r, t 即可。。
据说块大小为 N2/3 时复杂度最好可以达到 O(N5/3),然而 BZOJ 交上去还 N1/2 的要快。。
带修改莫队可以看这篇博客: https://www.cnblogs.com/zwfymqz/p/7154145.html。
Code: O(QlogQ+N1.5+QN0.5+QT) [5564K, 760MS]
其中 Q 为询问个数,T 为修改个数,满足 Q + T = M ≤ 10000。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; inline void getint(int &num){ char ch; while(!isdigit(ch = getchar())); num = ch - '0'; while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0'; } int N, M, a[10005]; int qcnt, mdcnt, bl[10005]; int S[1000005], curans, ans[10005]; char op[5]; struct Query{ int id, l, r, t; inline bool operator < (const Query &q2) const { if(bl[l] != bl[q2.l]) return l < q2.l; if(r != q2.r) return r < q2.r; return t < q2.t; } } q[10005]; struct Modify{ int pos, val; } md[10005]; inline void Mo_add(int pos) {if(++S[a[pos]] == 1) curans++;} inline void Mo_del(int pos) {if(--S[a[pos]] == 0) curans--;} inline void Mo_modify(int t, int id){ if(md[t].pos >= q[id].l && md[t].pos <= q[id].r){ if(--S[a[md[t].pos]] == 0) curans--; if(++S[md[t].val] == 1) curans++; } swap(md[t].val, a[md[t].pos]); } inline void Mo_with_modification(){ sort(q + 1, q + qcnt + 1); for(register int i = 1, l = 1, r = 0, t = 0; i <= qcnt; i++){ while(r < q[i].r) Mo_add(++r); while(r > q[i].r) Mo_del(r--); while(l < q[i].l) Mo_del(l++); while(l > q[i].l) Mo_add(--l); while(t < q[i].t) Mo_modify(++t, i); while(t > q[i].t) Mo_modify(t--, i); ans[q[i].id] = curans; } } int main(){ getint(N), getint(M); for(register int i = 1; i <= N; i++) getint(a[i]); for(register int i = 1; i <= M; i++){ scanf("%s", op); if(op[0] == 'Q'){ getint(q[++qcnt].l), getint(q[qcnt].r); q[qcnt].id = qcnt, q[qcnt].t = mdcnt; } else getint(md[++mdcnt].pos), getint(md[mdcnt].val); } int blocksize = (int)sqrt(N); for(register int i = 1; i <= N; i++) bl[i] = (i - 1) / blocksize + 1; Mo_with_modification(); for(register int i = 1; i <= qcnt; i++) printf("%d\n", ans[i]); return 0; }
发表评论