bzoj2120 数颜色 分块

分块大法好 orz

处理出每个点的前驱和后继位置。

暴力修改，查询就在每个整块里查询pre<l的，暴力跑两边就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 10005
using namespace std;
int n,m,nn,a[N],be[N],pre[N],nxt[N];
int last[1000005],pp[N],ans;
void work(int x){
	int l=(x-1)*nn+1,r=min(n,x*nn);
	for(int i=l;i<=r;i++)
		pp[i]=pre[i];
	sort(pp+l,pp+r+1);
}
void change(int x,int y){
	a[x]=y;
	if(nxt[x]){pre[nxt[x]]=pre[x];work(be[nxt[x]]);}
	if(pre[x]){nxt[pre[x]]=nxt[x];work(be[pre[x]]);}
	int pr=0,ne=0;
	for(int i=1;i<=n;i++){
		if(i<x&&a[i]==y) pr=i;
		if(i>x&&a[i]==y){ne=i;break;}
	}
	pre[x]=pr; nxt[x]=ne;
	work(be[x]); 
	 if(pr) {nxt[pr]=x;work(be[pr]);}
	 if(ne) {pre[ne]=x;work(be[ne]);}
}
int main()
{
	scanf("%d%d",&n,&m);
	nn=(int) sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		be[i]=(i-1)/nn+1;
	}
	for(int i=1;i<=n;i++){
		pre[i]=last[a[i]];
		last[a[i]]=i;
		if(pre[i]) nxt[pre[i]]=i;
	}
	int tot=be[n];
	for(int i=1;i<=tot;i++)work(i);
	char ch; int x,y,l,r,num;
	while(m--){
		ch=getchar();
		while(ch!='Q'&&ch!='R')ch=getchar();
		scanf("%d%d",&x,&y);
		if(ch=='Q'){
			ans=0;
			if(be[x]==be[y]){
				for(int i=x;i<=y;i++)if(pre[i]<x)ans++;
				printf("%d
",ans); continue;
			}
			for(int i=x;i<=be[x]*nn;i++)
				if(pre[i]<x) ans++;
			for(int i=(be[y]-1)*nn+1;i<=y;i++)
				if(pre[i]<x) ans++;
			for(int i=be[x]+1;i<be[y];i++){
				l=(i-1)*nn+1,r=min(n,i*nn); 
				num=lower_bound(pp+l,pp+r+1,x)-pp;
				ans+=num-l;
			}
			printf("%d
",ans);
		}
		if(ch=='R') change(x,y);
	}
	return 0;
}