P1903 [国家集训队] 数颜色 / 维护队列

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define pf first
#define pb push_back
#define ps second

#define rd read()
// #define nl putc('\n')
#define ot write
#define nl putchar('\n')
inline int rd
{
	int xx=0,ff=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') ff=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') xx=xx*10+(ch-'0'),ch=getchar();
	return xx*ff;
}
inline void write(int out)
{
	if(out<0) putchar('-'),out=-out;
	if(out>9) write(out/10);
	putchar(out%10+'0');
}


const int INF = 1e9;
const int N = 1e6+5;
const int S = 1e6+5;
const int maxlog = 18;

int n,m,mc,mq,len,res;
int cnt[N],w[N],ans[N];

struct query{
	int id,l,r,t;
}q[N];
struct node{
	int p,c;
}c[N];

int getKid(int x){
	return x/len;
}

bool cmp(query q1,query q2){
	int al=getKid(q1.l),ar=getKid(q1.r);
	int bl=getKid(q2.l),br=getKid(q2.r);
	if(al!=bl)return al<bl;
	if(ar!=br)return ar<br;
	return q1.t<q2.t;
}

void add(int x){
	if(!cnt[x])res++;
	cnt[x]++;
}

void del(int x){
	cnt[x]--;
	if(!cnt[x])res--;
}

signed main(){
	// ios::sync_with_stdio(false);
	// cin.tie(0),cout.tie(0);

	// n=rd,m=rd;
	// cin>>n>>m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&w[i]);//cin>>w[i];//w[i]=rd;
	for(int i=0;i<m;i++){
		char op[2];
		int a,b;
		scanf("%s%d%d",op,&a,&b);
		// cin>>op>>a>>b;
		if(*op=='Q'){
			mq++,q[mq]={mq,a,b,mc};
		}else{
			c[++mc]={a,b};
		}
	}

	// len=pow(1.00*n*mc,1.00/3)+1;//计算分块长度，是三次方根
	len=cbrt(1.00*n*mc)+1;//计算分块长度，是三次方根
    // len=sqrt(n)+1;
	sort(q+1,q+mq+1,cmp);

	int cl=0,cr=1,ct=0;
	for(int k=1;k<=mq;k++){
		int l=q[k].l,r=q[k].r,t=q[k].t;
		while(cl<r)cl++,add(w[cl]);
		while(cl>r)del(w[cl]),cl--;
		while(cr<l)del(w[cr]),cr++;
		while(cr>l)cr--,add(w[cr]);

		while(ct<t){
			ct++;
			if(c[ct].p>=cr&&c[ct].p<=cl)del(w[c[ct].p]),add(c[ct].c);
			swap(w[c[ct].p],c[ct].c);
		}
		while(ct>t){
			if(c[ct].p>=cr&&c[ct].p<=cl)del(w[c[ct].p]),add(c[ct].c);
			swap(w[c[ct].p],c[ct].c);
			ct--;
		}
		ans[q[k].id]=res;
	}
	for(int i=1;i<=mq;i++)printf("%d\n",ans[i]); //cout<<ans[i]<<'\n';
}



/*
2 5
0 1 1 1 1
0 1 1 2 4
0 2 1 2 1
0 2 1 1 4
*/