●洛谷P1903 [国家集训队]数颜色

题链：

https://www.luogu.org/problemnew/show/P1903
题解：

序列带修莫队，

复杂度$O(N^{\frac{5}{3}})$
代码：

include<bits/stdc++.h>

#define MAXN 10005

using namespace std;

int N,M,BLOCK,ans;

int color[1000006],s[MAXN],bel[MAXN],ANS[MAXN];

struct Query{

	int l,r,t,id;

	bool operator < (const Query &rtm) const{

		return bel[l]==bel[rtm.l]?(bel[r]==bel[rtm.r]?t<rtm.r:bel[r]<bel[rtm.r]):bel[l]<bel[rtm.l];

	}

}Q[MAXN];

struct Change{int p,newval,oldval;}C[MAXN];

int L=1,R,T;

void modify(int p,int k){

	color[s[p]]+=k;

	if(color[s[p]]==0&&k==-1) ans--;

	if(color[s[p]]==1&&k==1) ans++;

}

void dotime(int p,int v){

	if(L<=p&&p<=R) modify(p,-1),s[p]=v,modify(p,1);

	else s[p]=v;

}

int main(){

	static int now[MAXN];

	char ch; int x,y,qnt=0,tim=0;

	scanf("%d%d",&N,&M); BLOCK=pow(N,2.0/3);

	for(int i=1;i<=N;i++) bel[i]=i/BLOCK;

	for(int i=1;i<=N;i++) scanf("%d",&s[i]),now[i]=s[i];

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

		scanf(" %c%d%d",&ch,&x,&y);

		if(ch=='Q') qnt++,Q[qnt]=(Query){x,y,tim,qnt};

		else tim++,C[tim]=(Change){x,y,now[x]},now[x]=y;

	}

	sort(Q+1,Q+qnt+1);

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

		while(T<Q[i].t) T++,dotime(C[T].p,C[T].newval);

		while(T>Q[i].t) dotime(C[T].p,C[T].oldval),T--;

		while(R<Q[i].r) R++,modify(R,1);

		while(R>Q[i].r) modify(R,-1),R--;

		while(L<Q[i].l) modify(L,-1),L++;

		while(L>Q[i].l) L--,modify(L,1);

		ANS[Q[i].id]=ans;

	}

	for(int i=1;i<=qnt;i++) printf("%d\n",ANS[i]);

	return 0;

}

秒客网

●洛谷P1903 [国家集训队]数颜色

相关文章