bzoj 2120 数颜色带修改莫队

带修改莫队，每次查询前调整修改

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define N 20005

using namespace std;

int n,m,nn,a[N],be[N],l,r,num[1000005],tot,qq,cc;

bool vis[N];

struct Change{

	int pos,nxt,pre;

}ch[1005];

struct Query{

	int l,r,tim,id,ans;

}qr[10005];

bool cmp1(Query a,Query b){

	if(be[a.l]==be[b.l]) return a.r<b.r;

	return be[a.l]<be[b.l];

}

bool cmp2(Query a,Query b){

	return a.id<b.id;

}

void change(int pos,int now){

	if(pos>=l&&pos<=r){

		if(!(--num[a[pos]]))

			tot--;

		if(++num[now]==1)

			tot++;

	}

	a[pos]=now;

}

void update(int pos){

	if(vis[pos]){

		vis[pos]=0;

		if(!(--num[a[pos]]))

			tot--;

		return ;

	}

	if(!vis[pos]){

		vis[pos]=1;

		if(++num[a[pos]]==1)

			tot++;

		return ;

	}

}

void work(){

	l=1,r=0,tot=0;

	qr[0].tim=cc;

	for(int i=1;i<=qq;i++){

		//printf("%d  %d  %d  %d\n",qr[i].l,qr[i].r,qr[i].id,qr[i].tim);

		for(int j=qr[i-1].tim+1;j<=qr[i].tim;j++)

			change(ch[j].pos,ch[j].nxt);

		for(int j=qr[i-1].tim;j>qr[i].tim;j--)

			change(ch[j].pos,ch[j].pre);

		while(l<qr[i].l) update(l++);

		while(l>qr[i].l) update(--l);

		while(r<qr[i].r) update(++r);

		while(r>qr[i].r) update(r--);

		qr[i].ans=tot;

	}

}

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;

	}

	char s; int aa,bb;

	for(int i=1;i<=m;i++)

	{

		s=getchar();

		while(s!='Q'&&s!='R')s=getchar();

		scanf("%d%d",&aa,&bb);

		if(s=='R'){

			ch[++cc].pos=aa;

			ch[cc].nxt=bb;

			ch[cc].pre=a[aa];

			a[aa]=bb;

		}

		if(s=='Q'){

			qr[++qq].tim=cc;

			qr[qq].l=aa;

			qr[qq].r=bb;

			qr[qq].id=qq;

		}

	}

	sort(qr+1,qr+qq+1,cmp1);

	work();

	sort(qr+1,qr+qq+1,cmp2);

	for(int i=1;i<=qq;i++)

		printf("%d\n",qr[i].ans);

	return 0;

}

巴特西

bzoj 2120 数颜色带修改莫队

最新文章

热门文章

巴特西

bzoj 2120 数颜色 带修改莫队

最新文章

热门文章

bzoj 2120 数颜色带修改莫队