#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int N = 1e5 + 10, M = 1e5 + 10;
int n, m, t, mc, mq, res, a[N];
struct NODE{
	int l, r, id, ans, t, k;
}hh[N];
map <int, int> has;
struct Node {
	int a, b;
}c[M];

int get (int x)
{
	return x / cbrt((double)n * max(1 , mc)) + 1;
}

bool cmp (NODE a, NODE b)
{
	int al = get(a.l), ar = get(a.r);
    int bl = get(b.l), br = get(b.r);
    if (al != bl)
	{
		return al < bl;
	}
    if (ar != br)
	{
		return ar < br;
	}
    return a.t < b.t;
}

bool cmp2 (NODE x, NODE y)
{
	return x.id < y.id;
}

int main ()
{
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf ("%d", &a[i]);
	}
	for (int i = 1; i <= m; i++)
	{
		char op[2];
		int x, y;
		scanf ("%s%d%d", op, &x, &y);
		if (*op == 'C')
		{
			c[++mc] = {x, y};
		}
		else
		{
            int cv;
            scanf ("%d", &cv);
			hh[++mq].l = x;
            hh[mq].k = cv;
			hh[mq].r = y;
			hh[mq].id = i;
			hh[mq].t = mc;
		}
	}
	sort (hh + 1, hh + 1 + mq, cmp);
	int res = 0;
	for (int i = 1; i <= mq; i++)
	{
		if (hh[i - 1].l < hh[i].l)
		{
			for (int j = hh[i - 1].l; j < hh[i].l; j++)
			{
				has[a[j]]--;
			}
		}
		else
		{
			for (int j = hh[i].l; j < hh[i - 1].l; j++)
			{
				has[a[j]]++;
			}
		}
		if (hh[i - 1].r < hh[i].r)
		{
			for (int j = hh[i - 1].r + 1; j <= hh[i].r; j++)
			{
				has[a[j]]++;
			}
		}
		else
		{
			for (int j = hh[i].r + 1; j <= hh[i - 1].r; j++)
			{
				has[a[j]]--;
			}
		}
		if (hh[i - 1].t < hh[i].t)
		{
			for (int j = hh[i - 1].t + 1; j <= hh[i].t; j++)
			{
				if (c[j].a >= hh[i].l && c[j].a <= hh[i].r)
				{
					has[a[c[j].a]]--;
					swap (a[c[j].a], c[j].b);
					has[a[c[j].a]]++;
				}
				else
				{
					swap (a[c[j].a], c[j].b);
				}
			}
		}
		else if (hh[i - 1].t > hh[i].t)
		{
			for (int j = hh[i - 1].t; j > hh[i].t; j--)
			{
				if (c[j].a >= hh[i].l && c[j].a <= hh[i].r)
				{
					has[a[c[j].a]]--;
					swap (a[c[j].a], c[j].b);
					has[a[c[j].a]]++;
				}
				else
				{
					swap (a[c[j].a], c[j].b);
				}
			}
		}
		hh[i].ans = has[hh[i].k];
	}
	sort (hh + 1, hh + 1 + mq, cmp2);
	for (int i = 1; i <= mq; i++)
	{
		printf ("%d\n", hh[i].ans);
	}
	return 0;
}