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

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

思路：待修改莫队，增加一个时间戳，来维护当前询问的修改次数，如果修改多了就还原，否则修改到当前次数。

时间复杂度：$O(n^{\small\dfrac{5}{3}})$O(n35​)

具体看代码，我也是第一次写。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first
#define se second
#define pb push_back
template<class T>
inline void read(T &x){ 
	x=0;int w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	for(;ch>='0'&&ch<='9';ch=getchar())
		x=(x<<3)+(x<<1)+(ch&15);
	x*=w; 
}
template<class T>
inline void write(T x)
{
	if(!x)putchar('0');if(x<0)x=-x,putchar('-');
	static int sta[25];int tot=0;
	while(x)sta[tot++]=x%10,x/=10;
	while(tot)putchar(sta[--tot]+48);
}
int a[N],cnt[N],ans[N],bk[N];
struct query{	//储存查询信息 
	int l,r,id,t;
}q[N];
struct modify{ //储存修改信息. 
	int pos,c,pre;
}c[N];
int cntq,cntc,n,m,block,cntb;//cntq查询次数，cntc修改次数,block块的大小,cntb块的个数. 
bool cmp(query a,query b) {	//排序(第一关键字左端点块,第二关键字右端点块,第三关键字时间. 
	return (bk[a.l]^bk[b.l])?bk[a.l]<bk[b.l]:((bk[a.r]^bk[b.r])?bk[a.r]<bk[b.r]:a.t<b.t);
}
int main(){
	read(n),read(m),block=pow(n,2.0/3.0);
	cntb=ceil((double)n/block);
	for(int i=1;i<=cntb;i++)
		for(int j=(i-1)*block+1;j<=i*block;j++) bk[j]=i;
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=m;i++){
		char op[10];scanf("%s",op);
		if(op[0]=='Q'){
			read(q[++cntq].l),read(q[cntq].r);
			q[cntq].t=cntc;
			q[cntq].id=cntq;
		}
		else if(op[0]=='R')
			read(c[++cntc].pos),read(c[cntc].c);
	}
	sort(q+1,q+cntq+1,cmp);
	int l=1,r=0,time=0,now=0;//time表示当前被修改的次数,now表示当前答案. 
	for(int i=1;i<=cntq;i++){
		int ql=q[i].l,qr=q[i].r,qt=q[i].t;
		while(l < ql) now -= !--cnt[a[l++]];//删l 
		while(l > ql) now += !cnt[a[--l]]++;//增l 
		while(r < qr) now += !cnt[a[++r]]++;//增r 
		while(r > qr) now -= !--cnt[a[r--]];//删r 
		while(time<qt){//当被查询修改次数大了时,继续修改至该次数. 
			++time;	//如果在区间范围就更新. 
			if(ql<=c[time].pos&&c[time].pos<=qr) now -= !--cnt[a[c[time].pos]] - !cnt[c[time].c]++;
			swap(a[c[time].pos],c[time].c);
		}
		while(time>qt){//当被查询修改次数小了时,还原至该次数. 
			if(ql<=c[time].pos&&c[time].pos<=qr) now -= !--cnt[a[c[time].pos]] - !cnt[c[time].c]++;
			swap(a[c[time].pos],c[time].c);
			--time;
		}
		ans[q[i].id]=now;
	}
	for(int i=1;i<=cntq;i++)
		write(ans[i]),putchar('\n');
	return 0;
}