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

liuchanglc 2020-10-12 原文

题目描述

墨墨购买了一套\(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;
}