bzoj2120: 数颜色（带修改的莫队）

www.cnblogs.com/shaokele/

---

bzoj2120: 数颜色##

　　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
　　

题目地址：　　bzoj2120: 数颜色

题目大意： 　　题目很简洁了：）####

　　

题解：

　　带修改的莫队算法
　　
　　只不过排序时顺序要改一下
　　
　　把 (l) 作为第一关键字，在将 (r) 作为第二关键字
　　
　　再将询问之前有多少次修改作为第三关键字
　　
　　之后大暴力模拟就好了
　　
　　时间复杂度详见：AKteam
　　

bool cmp(query x,query y)
{//pos表示这个点所在的块
	if (pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];//先按左端点所在的块排序
	if (pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];//再按右端点所在的块排序
	else return x.pre<y.pre;//再按询问前的修改次数排序
}

---

AC代码

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=10005;
int n,m,totQ,totC;
int L,R,now,ans;
int a[N],b[N],pos[N],Ans[N];
int sum[1000005];
struct nodeQ{
	int l,r,pre,id;
}Q[N];
struct nodeR{
	int p,col,pre;
}C[N];
bool cmp(nodeQ a,nodeQ b){
	if(pos[a.l]!=pos[b.l])return pos[a.l]<pos[b.l];
	if(pos[a.r]!=pos[b.r])return pos[a.r]<pos[b.r];
	return a.pre<b.pre;
}
void modify(int pos,int col){
	if(L<=pos && pos<=R){
		if(--sum[a[pos]] ==0)ans--;
		if(sum[col]++ ==0)ans++;
	}
	a[pos]=col;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		b[i]=a[i];
	}
	scanf("
");
	for(int i=1;i<=m;i++){
		char op=getchar();
		if(op=='Q'){
			totQ++;
			scanf("%d%d
",&Q[totQ].l,&Q[totQ].r);
			Q[totQ].pre=totC;
			Q[totQ].id=totQ;
			
		}else{
			totC++;
			scanf("%d%d
",&C[totC].p,&C[totC].col);
			C[totC].pre=b[C[totC].p];
			b[C[totC].p]=C[totC].col;
		}
	}
	int X=pow(n,0.666);
	for(int i=1;i<=n;i++)
		pos[i]=(i-1)/X+1;
	sort(Q+1,Q+totQ+1,cmp);
	L=1,R=0,now=0,ans=0;
	for(int i=1;i<=totQ;i++){
		for(int k=now+1;k<=Q[i].pre;k++)
			modify(C[k].p,C[k].col);
		for(int k=now;k>=Q[i].pre+1;k--)
			modify(C[k].p,C[k].pre);
		now=Q[i].pre;
		while(R<Q[i].r)
			if(sum[a[++R]]++ ==0)ans++;
		while(L>Q[i].l)
			if(sum[a[--L]]++ ==0)ans++;
		while(R>Q[i].r)
			if(--sum[a[R--]] ==0)ans--;
		while(L<Q[i].l)
			if(--sum[a[L++]] ==0)ans--;
		Ans[Q[i].id]=ans;
	}
	for(int i=1;i<=totQ;i++)
		printf("%d
",Ans[i]);
	return 0;
}