墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

Q

Q

R

Q

Q  

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <algorithm>

#include <set>

using namespace std;

int read() {

	int x = 0, f = 1; char c = getchar();

	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }

	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }

	return x * f;

}

#define maxn 10010

#define maxcol 1000010

#define maxnode 7840010

int ToT, sumv[maxnode], lc[maxnode], rc[maxnode];

void update(int& y, int x, int l, int r, int p, int v) {

	sumv[y = ++ToT] = sumv[x] + v;

	if(l == r) return ;

	int mid = l + r >> 1; lc[y] = lc[x]; rc[y] = rc[x];

	if(p <= mid) update(lc[y], lc[x], l, mid, p, v);

	else update(rc[y], rc[x], mid + 1, r, p, v);

	return ;

}

int query(int o, int l, int r, int qr) {

	if(r <= qr) return sumv[o];

	int mid = l + r >> 1, ans = query(lc[o], l, mid, qr);

	if(qr > mid) ans += query(rc[o], mid + 1, r, qr);

	return ans;

}

int rt[maxn], Rt[maxn];

int n, A[maxn], pre[maxn], lst[maxcol];

void change(int p, int val) {

	for(int x = p; x <= n; x += x & -x)

		update(Rt[x], Rt[x], 0, n, pre[p], -1),

		update(Rt[x], Rt[x], 0, n, val, 1);

	pre[p] = val;

	return ;

}

int Art[maxn], cntA, Drt[maxn], cntD;

void getrt(int A[], int& cnt, int x) {

	cnt = 0;

	for(; x; x -= x & -x) A[++cnt] = Rt[x];

	return ;

}

int ask(int ql, int qr) {

	getrt(Art, cntA, qr); Art[++cntA] = rt[qr];

	getrt(Drt, cntD, ql - 1); Drt[++cntD] = rt[ql-1];

	int sum = 0;

	for(int i = 1; i <= cntA; i++) sum += query(Art[i], 0, n, ql - 1);

	for(int i = 1; i <= cntD; i++) sum -= query(Drt[i], 0, n, ql - 1);

	return sum;

}

set <int> colpos[maxcol];

int main() {

	n = read(); int q = read();

	for(int i = 0; i < maxcol; i++) colpos[i].insert(0);

	for(int i = 1; i <= n; i++) {

		A[i] = read();

		pre[i] = lst[A[i]];

		lst[A[i]] = i;

		colpos[A[i]].insert(i);

	}

	for(int i = 1; i <= n; i++) update(rt[i], rt[i-1], 0, n, pre[i], 1);

	char cmd[5];

	while(q--) {

		scanf("%s", cmd);

		if(cmd[0] == 'Q') {

			int l = read(), r = read();

			printf("%d\n", ask(l, r));

		}

		if(cmd[0] == 'R') {

			int p = read(), col = read();

			if(A[p] == col) continue;

			// it -> next  ttit -> now  tit -> pre

			set <int> :: iterator it = colpos[A[p]].lower_bound(p), tit = it, ttit;

			it++; tit--;

			if(it != colpos[A[p]].end()) change(*it, *tit);

			colpos[A[p]].erase(p);

			colpos[col].insert(p);

			it = colpos[col].lower_bound(p); ttit = tit = it;

			it++; tit--;

			if(it != colpos[col].end()) change(*it, *ttit);

			change(*ttit, *tit);

			A[p] = col;

		}

	}

	return 0;

}