记录编号	359536	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.274 s
提交时间	2016-12-23 14:38:18	内存使用	4.59 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 1e4 + 10;
const int MAXC = 1e6 + 10;


#define is_num(x) (x <= '9' and x >= '0')
inline int get_num() {
	char tmp = getchar();
	int res = 0;
	
	while (not is_num(tmp)) tmp = getchar();
	while (    is_num(tmp)) {
		res = (res << 3) + (res << 1) + tmp - '0';
		tmp = getchar();
	}
	
	return res;
}


#define is_han(x) (x == 'Q' or x == 'R')
inline int get_han() {
	char tmp = getchar();
	
	while (not is_han(tmp)) tmp = getchar();
	
	return tmp == 'Q' ? 1 : 2;
}


struct Question {
	int l, bl, r, br, ts, id;
	Question() {}
	Question(int l_, int bl_, int r_, int br_, int time_stemp, int id_) {
		l = l_, bl = bl_, r = r_, br = br_, ts = time_stemp, id = id_;
	}
	
	bool operator < (const Question &b) const {
		return bl == b.bl ? (br == b.br ? ts < b.ts : br < b.br) : (bl < b.bl);
	}
} qs[MAXN];

struct Change {
	int tar, last, to;
	Change() {}
	Change(int tar_, int last_, int to_) { tar = tar_, last = last_, to = to_; }
} cs[MAXN];

int qcnt, ccnt;
int n, m;
int global_ans[MAXN];
int la[MAXN], col[MAXN];
int cnt[MAXC];


inline void read() {
	n = get_num();
	m = get_num();
	for (int i = 1; i <= n; i++) la[i] = col[i] = get_num();
	int blksz = (int)pow(n, 2.0 / 3.0);
	
	for (int i = 1; i <= m; i++) {
		int han = get_han();

		if (han == 1) {
			int l = get_num(), r = get_num();
			qs[++qcnt] = Question(l, (l - 1) / blksz + 1, r, (r - 1) / blksz + 1, ccnt, qcnt);
		} else {
			int tar = get_num(), to = get_num();
			cs[++ccnt] = Change(tar, la[tar], to), la[tar] = to;
		}
	}
}


inline void insert(int tar, int &ans) {
	if (cnt[col[tar]]++ == 0) ans++;
}


inline void erase(int tar, int &ans) {
	if (--cnt[col[tar]] == 0) ans--;
}


inline void modify(int tnow, int l, int r, int &ans, bool demod = false) {
	if (cs[tnow].tar <= r and cs[tnow].tar >= l) {
		erase(cs[tnow].tar, ans);
		col[cs[tnow].tar] = demod ? cs[tnow].last : cs[tnow].to;
		insert(cs[tnow].tar, ans);
	} else col[cs[tnow].tar] = demod ? cs[tnow].last : cs[tnow].to;;
}


inline void solve() {
	sort(qs + 1, qs + qcnt + 1);
	int tnow = 0, lnow = 1, rnow = 0, ans = 0;
		
	for (int i = 1; i <= qcnt; i++) {
		while (tnow < qs[i].ts) modify(++tnow, lnow, rnow, ans);
		while (tnow > qs[i].ts) modify(tnow--, lnow, rnow, ans, true);
		
		while (lnow < qs[i].l) erase(lnow++, ans);
		while (lnow > qs[i].l) insert(--lnow, ans);
		while (rnow > qs[i].r) erase(rnow--, ans);
		while (rnow < qs[i].r) insert(++rnow, ans);
		
		global_ans[qs[i].id] = ans;
	}
	
	for (int i = 1; i <= qcnt; i++) {
		printf("%d\n", global_ans[i]);
	}
}


int main() {
#ifdef LOCAL
	freopen("test.in", "r", stdin);
#elif not defined BAT
	freopen("nt2011_color.in", "r", stdin);
	freopen("nt2011_color.out", "w", stdout);
#endif
	read();
	solve();
	return 0;
}