你小时候玩过弹珠吗？

小朋友A有一些弹珠，A喜欢把它们排成队列，从左到右编号为1到N。为了整个队列鲜艳美观，小朋友想知道某一段连续弹珠中，不同颜色的弹珠有多少。当然，A有时候会依据个人喜好，替换队列中某个弹珠的颜色。但是A还没有学过编程，且觉得头脑风暴太浪费脑力了，所以向你来寻求帮助。

输入文件第一行包含两个整数N和M。

第二行N个整数，表示初始队列中弹珠的颜色。

接下来M行，每行的形式为“Q L R”或“R x c”，“Q L R”表示A想知道从队列第L个弹珠到第R个弹珠中，一共有多少不同颜色的弹珠，“R x c”表示A把x位置上的弹珠换成了c颜色。

对于每个Q操作，输出一行表示询问结果。

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
int n , si , c[10010] , vc[10010] , p[10010] , vp[10010] , last[1000010];
char str[5];
void reset(int b)
{
	int l = b * si , r = min((b + 1) * si - 1 , n - 1) , i;
	for(i = l ; i <= r ; i ++ ) vc[i] = c[i] , vp[i] = p[i];
	sort(vc + l , vc + r + 1) , sort(vp + l , vp + r + 1);
}
int query(int b , int lim)
{
	int l = b * si , r = min((b + 1) * si - 1 , n - 1) , mid , ans = l - 1 , tl = l;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(vp[mid] < lim) ans = mid , l = mid + 1;
		else r = mid - 1;
	}
	return ans - tl + 1;
}
bool findc(int l , int r , int x)
{
	int mid;
	while(l <= r)
	{
		mid = (l + r) >> 1;
		if(vc[mid] == x) return 1;
		else if(vc[mid] < x) l = mid + 1;
		else r = mid - 1;
	}
	return 0;
}
int main()
{
	int m , i , j , x , y , ans , flag , l , r;
	scanf("%d%d" , &n , &m);
	si = (int)sqrt(n);
	memset(last , -1 , sizeof(last));
	for(i = 0 ; i < n ; i ++ ) scanf("%d" , &c[i]) , p[i] = last[c[i]] , last[c[i]] = i;
	for(i = 0 ; i * si < n ; i ++ ) reset(i);
	while(m -- )
	{
		scanf("%s%d%d" , str , &x , &y);
		x -- ;
		if(str[0] == ‘Q‘)
		{
			y -- ;
			ans = 0;
			if(x / si == y / si) for(i = x ; i <= y ; i ++ ) ans += (p[i] < x);
			else
			{
				for(i = x / si + 1 ; i < y / si ; i ++ ) ans += query(i , x);
				for(i = x ; i < (x / si + 1) * si ; i ++ ) ans += (p[i] < x);
				for(i = y / si * si ; i <= y ; i ++ ) ans += (p[i] < x);
			}
			printf("%d\n" , ans);
		}
		else
		{
			if(c[x] == y) continue;
			flag = 0;
			for(i = x + 1 ; !flag && i < (x / si + 1) * si && i < n ; i ++ ) if(p[i] == x) p[i] = p[x] , reset(i / si) , flag = 1;
			for(i = x / si + 1 ; !flag && i * si < n ; i ++ )
			{
				l = i * si , r = min((i + 1) * si - 1 , n - 1);
				if(findc(l , r , c[x])) for(j = l ; !flag && j <= r ; j ++ ) if(c[j] == c[x]) p[j] = p[x] , reset(i) , flag = 1;
			}
			c[x] = y;
			flag = 0;
			for(i = x + 1 ; !flag && i < (x / si + 1) * si && i < n ; i ++ ) if(c[i] == c[x]) p[i] = x , reset(i / si) , flag = 1;
			for(i = x / si + 1 ; !flag && i * si < n ; i ++ )
			{
				l = i * si , r = min((i + 1) * si - 1 , n - 1);
				if(findc(l , r , c[x])) for(j = l ; !flag && j <= r ; j ++ ) if(c[j] == c[x]) p[j] = x , reset(i) , flag = 1;
			}
			flag = 0;
			for(i = x - 1 ; !flag && i >= x / si * si ; i -- ) if(c[i] == c[x]) p[x] = i , flag = 1;
			for(i = x / si - 1 ; !flag && ~i ; i -- )
			{
				l = i * si , r = min((i + 1) * si - 1 , n - 1);
				if(findc(l , r , c[x])) for(j = r ; !flag && j >= l ; j -- ) if(c[j] == c[x]) p[x] = j , flag = 1;
			}
			if(!flag) p[x] = -1;
			reset(x / si);
		}
	}
}