BZOJ 2453 维护队列 题解

带修莫队模板，双倍经验，注意 add 和 del 的顺序以及数据范围（洛谷上）。

//bzoj#2453. 维护队列
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN=140000;
struct Change
{
	int pos,col,lst;
}c[MAXN];
struct Query
{
	int l,r,id,ts/*timestamp,时间戳*/;
}q[MAXN];
int n,m,t,num,idxc,idxq,a[MAXN],cnt[MAXN*20],belong[MAXN],tim,now,ans[MAXN];
char op[10];
bool cmp(Query a,Query b)
{
	return (belong[a.l]^belong[b.l])?belong[a.l]<belong[b.l]:((belong[a.r]^belong[b.r])?belong[a.r]<belong[b.r]:a.ts<b.ts);
}
void add(int x)
{
	if(!cnt[x]++)
	{
		now++;
	}
	return;
}
void del(int x)
{
	if(!--cnt[x])
	{
		now--;
	}
	return;
}
int main()
{
	int ql,qr,qt,l,r;
	scanf("%d%d",&n,&m);
	t=pow(n*1.0,2.0/3.0);
	num=ceil(n*1.0/t);
	for(int i=1;i<=num;i++)
	{
		for(int j=(i-1)*t+1;j<=i*t;j++)
		{
			belong[j]=i;
		}
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%s %d %d",op,&l,&r);
		if(op[0]=='R')
		{
			c[++idxc].pos=l;
			c[idxc].col=r;
		}
		else if(op[0]=='Q') 
		{
			q[++idxq].l=l;
			q[idxq].r=r;
			q[idxq].id=idxq;
			q[idxq].ts=idxc;
		}
	}
	sort(&q[1],&q[idxq+1],cmp);
	l=1;
	r=0;
	for(int i=1;i<=idxq;i++)
	{
		ql=q[i].l;
		qr=q[i].r;
		qt=q[i].ts;
		while(l<ql)
		{
			del(a[l++]);
		}
		while(l>ql)
		{
			add(a[--l]);
		}
		while(r<qr)
		{
			add(a[++r]);
		}
		while(r>qr)
		{
			del(a[r--]);
		}
		while(tim<qt)
		{
			tim++;
			if(ql<=c[tim].pos&&qr>=c[tim].pos)
			{
				now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
			}
			swap(a[c[tim].pos],c[tim].col);
		}
		while(tim>qt)
		{
			if(ql<=c[tim].pos&&qr>=c[tim].pos)
			{
				now-=!--cnt[a[c[tim].pos]]-!cnt[c[tim].col]++;
			}
			swap(a[c[tim].pos],c[tim].col);
			tim--;
		}
		ans[q[i].id]=now;
	}
	for(int i=1;i<=idxq;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}
/*
 * HydroOJ-BZOJ
 * https://hydro.ac/d/bzoj/p/2453
 * C++20 -O2
 * 2022.10.2
 */