洛谷 P1903 [国家集训队]数颜色 / 维护队列带修莫队

题目描述

墨墨购买了一套\(N\)支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

\(1\)、 \(Q\) \(L\) \(R\)代表询问你从第\(L\)支画笔到第\(R\)支画笔中共有几种不同颜色的画笔。

\(2\)、 \(R\) \(P\) \(Col\) 把第\(P\)支画笔替换为颜色\(Col\)。

为了满足墨墨的要求，你知道你需要干什么了吗？

输入格式

第\(1\)行两个整数\(N\)，\(M\)，分别代表初始画笔的数量以及墨墨会做的事情的个数。

第\(2\)行\(N\)个整数，分别代表初始画笔排中第\(i\)支画笔的颜色。

第\(3\)行到第\(2+M\)行，每行分别代表墨墨会做的一件事情，格式见题干部分。

输出格式

对于每一个\(Query\)的询问，你需要在对应的行中给出一个数字，代表第\(L\)支画笔到第\(R\)支画笔中共有几种不同颜色的画笔。

输入输出样例

输入 #1

6 5

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

输出 #1

4

4

3

4

说明/提示

对于\(30\%\)的数据，\(n,m \leq 10000\)

对于\(60\%\)的数据，\(n,m \leq 50000\)

对于所有数据，\(n,m \leq 133333\)

所有的输入数据中出现的所有整数均大于等于\(1\)且不超过\(10^6\)。

本题可能轻微卡常数

分析

带修改操作的莫队，比普通的莫队多了一维时间的限制

此时我们的块长需要调整至 \(n^{\frac{2}{3}}\)

排序时：

第一关键字：左端点所在块编号，从小到大排序

第二关键字：右端点所在块编号，从小到大排序

第三关键字：经历的修改次数。也可以说是询问的先后，先询问的排前面

代码

#include<cstdio>

#include<cmath>

#include<algorithm>

#define rg register

inline int read(){

	rg int x=0,fh=1;

	rg char ch=getchar();

	while(ch<'0' || ch>'9'){

		if(ch=='-') fh=-1;

		ch=getchar();

	}

	while(ch>='0' && ch<='9'){

		x=(x<<1)+(x<<3)+(ch^48);

		ch=getchar();

	}

	return x*fh;

}

const int maxn=150000,maxm=1e6+5;

struct asd{

	int l,r,c,id;

	asd(){}

	asd(int aa,int bb,int cc,int dd){

		l=aa,r=bb,c=cc,id=dd;

	}

}b[maxn];

int n,m,a[maxn],shuyu[maxn],q[maxn][3],cnt1,cnt2,d[maxn],blo,sum[maxm],ans[maxn],tot;

char s[10];

bool cmp(asd aa,asd bb){

	if(shuyu[aa.l]==shuyu[bb.l] && shuyu[aa.r]==shuyu[bb.r]){

		return aa.id<bb.id;

	} else if(shuyu[aa.l]==shuyu[bb.l]){

		if(shuyu[aa.l]&1) return aa.r<bb.r;

		else return aa.r>bb.r;

	} else {

		return aa.l<bb.l;

	}

};

inline void xg(int now,int op){

	if(sum[now]==0) tot++;

	sum[now]+=op;

	if(sum[now]==0) tot--;

}

int main(){

	n=read(),m=read();

	blo=pow(n,(double)2/(double)3);

	for(rg int i=1;i<=n;i++){

		a[i]=read();

		d[i]=a[i];

		shuyu[i]=(i-1)/blo+1;

	}

	rg int aa,bb;

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

		scanf("%s",s+1);

		aa=read(),bb=read();

		if(s[1]=='Q'){

			cnt1++;

			b[cnt1]=asd(aa,bb,cnt2,cnt1);

		} else {

			cnt2++;

			q[cnt2][0]=aa,q[cnt2][1]=d[aa],q[cnt2][2]=bb;

			d[aa]=bb;

		}

	}

	std::sort(b+1,b+1+cnt1,cmp);

	rg int l=1,r=0,lat=0;

	for(rg int i=1;i<=cnt1;i++){

		while(lat<b[i].c){

			lat++;

			if(l<=q[lat][0] && r>=q[lat][0]){

				xg(q[lat][1],-1);

				xg(q[lat][2],1);

			}

			a[q[lat][0]]=q[lat][2];

		}

		while(lat>b[i].c){

			if(l<=q[lat][0] && r>=q[lat][0]){

				xg(q[lat][2],-1);

				xg(q[lat][1],1);

			}

			a[q[lat][0]]=q[lat][1];

			lat--;

		}

		while(l>b[i].l){

			l--;

			xg(a[l],1);

		}

		while(r<b[i].r){

			r++;

			xg(a[r],1);

		}

		while(l<b[i].l){

			xg(a[l],-1);

			l++;

		}

		while(r>b[i].r){

			xg(a[r],-1);

			r--;

		}

		ans[b[i].id]=tot;

	}

	for(rg int i=1;i<=cnt1;i++){

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

	}

	return 0;

}

巴特西

洛谷 P1903 [国家集训队]数颜色 / 维护队列带修莫队

题目描述

输入格式

输出格式

输入输出样例

输入 #1

输出 #1

说明/提示

分析

代码

最新文章

热门文章

巴特西

洛谷 P1903 [国家集训队]数颜色 / 维护队列 带修莫队

题目描述

输入格式

输出格式

输入输出样例

输入 #1

输出 #1

说明/提示

分析

代码

最新文章

热门文章

洛谷 P1903 [国家集训队]数颜色 / 维护队列带修莫队