#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ABC{
	int l,r,t,num;
}b[2000005];
struct AB{
	int a,b;
}ch[2000005];
int n,m,cnt1,cnt2,s,sum;
int a[2000005];
int c[10000005];
int ans[2000005];
bool cmp(ABC a,ABC b)
{
	if(a.l/s!=b.l/s)	return a.l<b.l;
	if(a.r/s!=b.r/s)
	{
		if((a.l/s)&1)	return a.r<b.r;
		return	a.r>b.r;
	}
	if((a.r/s)&1)	return a.t<b.t;
	return a.t>b.t;
//	return a.r<b.r;
}
inline void add(int x)
{
	sum+=!c[x]++;
}
inline void del(int x)
{
	sum-=!--c[x];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
	}
	for(register int i=1;i<=m;++i)
	{
		char z;
		int x,y;
		scanf("\n%c%d%d",&z,&x,&y);
		if(z=='Q')
		{
			b[++cnt1].l=x;
			b[cnt1].r=y;
			b[cnt1].t=cnt2;
			b[cnt1].num=cnt1;
		}
		else
		{
			ch[++cnt2].a=x;
			ch[cnt2].b=y;
		}
	}
	for(;s*s*s<n*n;++s);
	s=max(s,1);
	sort(b+1,b+cnt1+1,cmp);
	int l=b[1].l,r=b[1].l-1,t=0;
	for(register int i=1;i<=m;i++)
	{
		for(;l>b[i].l;)
		{
			add(a[--l]);
		}
		for(;r<b[i].r;)
		{
			add(a[++r]);
		}
		for(;l<b[i].l;)
		{
			del(a[l++]);
		}
		for(;r>b[i].r;)
		{
			del(a[r--]);
		}
		for(;t<b[i].t;)
		{
			int tmp=a[ch[++t].a];
			a[ch[t].a]=ch[t].b;
			if(b[i].l<=ch[t].a&&ch[t].a<=b[i].r)
			{
				del(tmp);
				add(ch[t].b);
			}
			ch[t].b=tmp;
		}
		for(;t>b[i].t;)
		{
			int tmp=a[ch[t].a];
			a[ch[t].a]=ch[t].b;
			if(b[i].l<=ch[t].a&&ch[t].a<=b[i].r)
			{
				del(tmp);
				add(ch[t].b);
			}
			ch[t--].b=tmp;
		}
		ans[b[i].num]=sum;
	}
	for(register int i=1;i<=cnt1;i++)
	{
		printf("%d\n",ans[i]);
	}
	return 0;
}

记录详情