省流：把块的大小改为pow(n,0.666)

附上AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=2000005;
char c;
int n,m,x,y,la,be[N],a[N],vis[N],now,K,tot1,tot2;
int l,r,ans[N];
int read()
{
	int x=0;char c;bool f=false;
	c=getchar();if (c=='-') f=1;
	while (c<'0'||c>'9') {c=getchar();if (c=='-') f=1;}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	if (f) x=x*-1;
	return x;
}

struct mmp1
{
	int id,color,la;
}change[N];

struct mmp
{
	int l,r,la,id;
}ask[N];

bool cmp(mmp x,mmp y)
{
	
	if (be[x.l]==be[y.l]) 
	{
		if (be[x.r]==be[y.r]) return x.la<y.la;
		else return x.r<y.r;
	}
	return be[x.l]<be[y.l];
}

void add(int id)
{
	if (!vis[a[id]]) now++;
	vis[a[id]]++;
}

void del(int id)
{
	vis[a[id]]--;
	if (!vis[a[id]]) now--;
}

void updata(int res,int L,int R)//L-R内的改动才对答案有贡献 
{
	if (change[res].id>=L&&change[res].id<=R)
	{
		if (--vis[a[change[res].id]]==0) now--;
		if (++vis[change[res].color]==1) now++;
	}
	swap(change[res].color,a[change[res].id]);//pos=id  val=color
	//这里有个很巧妙的操作 
    //对于一个操作，下一次需要为的颜色是本次被改变的颜色
    //比如，我把颜色3改为了7，那么再进行这次修改的时候就是把7改为3
    //所以直接交换两种颜色就好 
}

int main() 
{
//	freopen("1.in","r",stdin);
	n=read();m=read();K=pow(n,0.666);
	for (int i=1;i<=n;i++)
	a[i]=read(),be[i]=(i+K-1)/K;
	tot1=0;tot2=0;//查询 修改次数 
	for (int i=1;i<=m;i++)
	{
		cin>>c;x=read();y=read();
		if (c=='Q') tot1++,ask[tot1].l=x,ask[tot1].r=y,ask[tot1].la=la,ask[tot1].id=tot1;
		else tot2++,change[tot2].id=x,change[tot2].color=y,la=tot2,change[tot2].la=a[x];
	}
	sort(1+ask,1+ask+tot1,cmp);
	l=r=0;now=0;la=0;//当前的总数，当前最后一次改是版本几 
	for (int i=1;i<=tot1;i++)
	{
		while (l<ask[i].l) del(l),l++;
		while (l>ask[i].l) add(l-1),l--;
		while (r<ask[i].r) add(r+1),r++;
		while (r>ask[i].r) del(r),r--;
		while (la<ask[i].la) la++,updata(la,ask[i].l,ask[i].r);//更新 
		while (la>ask[i].la) updata(la,ask[i].l,ask[i].r),la--;//回退 
		//la表示当前的版本 
		ans[ask[i].id]=now;
	}
	for (int i=1;i<=tot1;i++)
	cout<<ans[i]<<endl; 
    return 0;
}
/*
1
4 1000
2 3 4 5
*/

从76-AC的关键就是代码第69行，从之前的K=sqrt(n)改成了K=pow(n,0,666)，也就是调整分块时块的大小。可以证明当块的大小接近2/3时更优，关于复杂度的证明可以自行百度。