[BZOJ 2120][国家集训队2011] 数颜色【带修改莫队】

  • 2018-01-28
  • 0
  • 0

Problem:

Time Limit: 6 Sec  Memory Limit: 259 MB

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;
}

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai