[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;
}
发表评论