golB s'CBoriN

分块大法好！块的个数=BLOCK 每块大小=STEP bloans[L][R](1<=L<=R<=BLOCK)表示第L个块至第R个块的答案，每次修改都可以BLOCK^2维护bloans的值，询问时先算出完整的块时的答案 再在两端补上去，可在O(STEP)时间内完成。

这个先自嘲以下数学，BLOCK的大小，我是用N的大小、Q的个数和R的个数算的，理论上的最优值，不过并没有什么卵用

#include <cstdio>
#include <algorithm>
int N,Q,BLOCK,STEP,bloans[400][400],cnt[400][20001],co[10001],q[10001][3],A[20001],v[20001],HASH;
int sqrt3(int x)
{
	int l,r;
	if (x<=1000)
		l=0,r=10;
	else
		if (x<=50000)
			l=11,r=36;
		else
			l=37,r=100;
	while (l<r)
	{
		int m=l+r+1>>1;
		if (m*m*m<=x)
			l=m;
		else
			r=m-1;
	}
	return l;
}
void init()
{
	scanf("%d%d",&N,&Q);
	for (int i=1;i<=N;i++)
		scanf("%d",&co[i]),A[i]=co[i];
	HASH=N;
	int nQ=0,nR=0;
	for (int i=1;i<=Q;i++)
	{
		char c=getchar();
		while (c!='Q'&&c!='R')
			c=getchar();
		q[i][0]=(c=='R');
		scanf("%d%d",&q[i][1],&q[i][2]);
		if (q[i][0])
			A[++HASH]=q[i][2];
	}
	std::sort(A+1,A+HASH+1);
	HASH=std::unique(A+1,A+HASH+1)-A-1;
	for (int i=1;i<=N;i++)
		co[i]=std::lower_bound(A+1,A+HASH+1,co[i])-A;
	for (int i=1;i<=Q;i++)
		if (q[i][0])
			nR++,q[i][2]=std::lower_bound(A+1,A+HASH+1,q[i][2])-A;
		else
			nQ++;
	BLOCK=sqrt3(N*(nQ+1)/(nR+1)/2);
	if (BLOCK>N)
		BLOCK=N;
	if (BLOCK>380)
		BLOCK=380;
	if (BLOCK<1)
		BLOCK=1;
	STEP=N/BLOCK;
	for (int l=1;l<=BLOCK;l++)
	{
		bloans[l][l-1]=0;
		for (int i=1;i<=HASH;i++)
			v[i]=0;
		for (int r=l;r<=BLOCK;r++)
		{
			bloans[l][r]=bloans[l][r-1];
			for (int i=(r-1)*STEP+1;i<=r*STEP;i++)
				if (!v[co[i]])
					v[co[i]]=1,bloans[l][r]++;
		}
	}
	for (int i=1;i<=HASH;i++)
		v[i]=0;
	for (int i=1;i<=BLOCK*STEP;i++)
		cnt[(i+STEP-1)/STEP][co[i]]++;
	for (int i=2;i<=BLOCK;i++)
		for (int j=1;j<=HASH;j++)
			cnt[i][j]+=cnt[i-1][j];
}
void Re(int p,int d)
{
	if (co[p]==d)
		return;
	int IBR=(p+STEP-1)/STEP;
	if (IBR<=BLOCK)
	{
		for (int i=1;i<=IBR;i++)
			for (int j=IBR;j<=BLOCK;j++)
			{
				if (cnt[j][co[p]]-cnt[i-1][co[p]]==1)
					bloans[i][j]--;
				if (cnt[j][d]-cnt[i-1][d]==0)
					bloans[i][j]++;
			}
		for (int i=IBR;i<=BLOCK;i++)
			cnt[i][co[p]]--,cnt[i][d]++;
	}
	co[p]=d;
}
int Qu(int ti,int l,int r)
{
	int LBR=(l+STEP+STEP-2)/STEP,RBR=r/STEP,OUT=0;
	if (RBR>BLOCK)
		RBR=BLOCK;
	if (LBR>RBR)
	{
		for (int i=l;i<=r;i++)
			if (v[co[i]]!=ti)
				v[co[i]]=ti,OUT++;
		return OUT;
	}
	else
	{
		OUT=bloans[LBR][RBR];
		for (int i=(LBR-1)*STEP;i>=l;i--)
			if (v[co[i]]!=ti&&cnt[RBR][co[i]]-cnt[LBR-1][co[i]]==0)
				v[co[i]]=ti,OUT++;
		for (int i=RBR*STEP+1;i<=r;i++)
			if (v[co[i]]!=ti&&cnt[RBR][co[i]]-cnt[LBR-1][co[i]]==0)
				v[co[i]]=ti,OUT++;
		return OUT;
	}
}
int main()
{
	init();
	for (int i=1;i<=Q;i++)
		if (q[i][0])
			Re(q[i][1],q[i][2]);
		else
			printf("%d\n",Qu(i,q[i][1],q[i][2]));
	return 0;
}