[國家集訓隊]數顔色 / 維護隊列

題目

發現帶修莫隊就是一個不優美的莫隊\(trick\)

我們發現我們的莫隊現在有了單點修改

那麼我們對于一個詢問就表示成一個三元組\((l,r,t)\)，第三維是時間

我們預處理出每一個詢問距離在他之前距離他最近的修改操作

最優分塊大小是\(n^{\frac{2}{3}}\)

排序的話如果左端點不在同一個塊裡按照左端點排序，否則右端點在不同一個塊裡按照右端點排序，否則按照時間排序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define re register
#define LL long long
const int maxn=50005;
inline int read() {
	char c=getchar();int x=0;while(c<'0'||x>'9') c=getchar();
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct Ask{int l,r,t,rk;}q[maxn];
int col[maxn],pos[maxn],id[maxn],Ans[maxn],val[maxn],num[1000005];
int n,m,tot,cnt,sz,ans;
inline int cmp(Ask A,Ask B) {
	if(id[A.l]!=id[B.l]) return id[A.l]<id[B.l];
	if(id[A.r]!=id[B.r]) return id[A.r]<id[B.r];
	return A.t<B.t;
}
inline void add(int x) {
	if(!num[x]) ++ans;num[x]++;
}
inline void del(int x) {
	num[x]--;if(!num[x]) --ans;
}
inline void change(int now,int i) {
	if(pos[now]>=q[i].l&&pos[now]<=q[i].r) {
		del(col[pos[now]]);
		add(val[now]);
	}
	std::swap(col[pos[now]],val[now]);
    //這裡有一個小trick
    //我們接下來可能還需要退回這次修改操作，于是我們隻需要交換這個位置的顔色和修改之後的顔色就可以了，這樣再執行到這裡的時候就可以直接還原回去了
}
int main() {
	n=read(),m=read();sz=pow(n,0.6666666);
	for(re int i=1;i<=n;i++) col[i]=read(),id[i]=(i-1)/sz+1;
	char opt[3];
	for(re int i=1;i<=m;i++) {
		scanf("%s",opt);
		if(opt[0]=='Q') {
			q[++cnt].l=read();q[cnt].r=read();
			q[cnt].rk=cnt,q[cnt].t=tot;
		}
		else {
			pos[++tot]=read();
			val[tot]=read();
		}
	}
	std::sort(q+1,q+cnt+1,cmp);
	int l=0,r=0,now=0;
	for(re int i=1;i<=cnt;i++) {
		while(r<q[i].r) ++r,add(col[r]);
		while(l>q[i].l) --l,add(col[l]);
		while(r>q[i].r) del(col[r]),r--;
		while(l<q[i].l) del(col[l]),l++;
		while(now>q[i].t) change(now--,i);
		while(now<q[i].t) change(++now,i);
		Ans[q[i].rk]=ans;
	}
	for(re int i=1;i<=cnt;i++) printf("%d\n",Ans[i]);
	return 0;
}