[国家集训队] 数颜色 / 维护队列(过程看注释)

题目描述

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

1. $QLR$ 代表询问你从第 $L$ 支画笔到第 $R$ 支画笔中共有几种不同颜色的画笔。

2. $RPCol$ 把第 $P$ 支画笔替换为颜色 $Col$。

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #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\le 10000$

对于60%的数据，$n,m\le 50000$

对于所有数据，$n,m\le 133333$

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

本题可能轻微卡常数

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
typedef long long ll;
struct modui{
    int l,r,t,id;
}s[N];
int n,m,a[N],c[N],d[N],pos[N],ans=0,L=1,R=0,T=0,ls=0,k;
int pre[N],nex[N],anss[N];
char ch[2];
void add(int x){
	if(c[x]==0) ans++;//此时为0，新增就意味着新颜色的出现
	c[x]++;
}
void del(int x){
	c[x]--;
	if(c[x]==0) ans--;//删掉后为0，意味着一种颜色的消失
}
bool cmp(modui &x,modui &y){//以左端点所在块为第一关键字，以右端点所在块为第二关键字
	//以时间为第三关键字进行排序
	if (pos[x.l]!=pos[y.l]) return x.l<y.l;
    if(pos[x.r]!=pos[y.r]) return x.r<y.r;
	return x.t<y.t;//都是为了加速
}
void query(int l,int r,int t,int id){//移动指针的时候，对应地去删除或添加对答案的贡献
	//如果当前修改数比询问的修改数少就把没修改的进行修改，反之回退
	while (L<l) del(a[L++]);//左指针往右移删除
	while (L>l) add(a[--L]);//左指针往左移加入
	while (R<r) add(a[++R]);//右指针往右移加入
	while (R>r) del(a[R--]);//右指针往左移删除
	while(T<t){//增加T这个修改
		T++;
		if(L<=pre[T]&&pre[T]<=R) del(a[pre[T]]);//删掉旧的
		d[T]=a[pre[T]];//记录下修改之前的信息，方便还原
		a[pre[T]]=nex[T];
		if(L<=pre[T]&&pre[T]<=R) add(a[pre[T]]);//改来新的
	}
	while(T>t){//回撤T这个修改
		if(L<=pre[T]&&pre[T]<=R) del(a[pre[T]]);//删掉多的
		a[pre[T]]=d[T];//回撤
		if(L<=pre[T]&&pre[T]<=R) add(a[pre[T]]);//还原旧的
		T--;
	}
	anss[id]=ans;//记录答案
	return;
}
int main(){
	cin>>n>>m;
    int dis=pow(n,(double)2/(double)3);//块大小 
    //pos标记每个数所属的分块
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[i]=i/dis;
	for(int i=1;i<=m;i++){
		scanf("%s",ch);
		int l,r;
		scanf("%d %d",&l,&r);
		if(ch[0]=='Q') s[++ls]=modui{l,r,k,ls};
		else k++,pre[k]=l,nex[k]=r;
	}
	sort(s+1,s+1+ls,cmp);
	for(int i=1;i<=ls;i++)  query(s[i].l,s[i].r,s[i].t,s[i].id);
	for(int i=1;i<=ls;i++)  printf("%d\n",anss[i]);
	return 0;
}