记录编号	574868	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]数颜色	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.223 s
提交时间	2022-08-26 20:49:03	内存使用	9.47 MiB

#include <bits/stdc++.h>

struct Q { int l, r, tim, id, ans; };
struct C { int pos, Old, New; };

const int N = 50010, M = 1e6+10;
int n, m, t, l = 1, r, T, cnt, tim, ans;
int a[N], b[N], pos[N], now[N], color[M];
Q q[N];
C c[N];

bool cmp1(Q a, Q b) { return pos[a.l] == pos[b.l] ? (pos[a.r] == pos[b.r] ? a.tim < b.tim : a.r < b.r) : a.l < b.l; }
bool cmp2(Q a, Q b) { return a.id < b.id; }

void revise(int col, int op) {
	color[col] += op;
	if (op > 0) ans += color[col] == 1;
	else ans -= color[col] == 0;
}

void work(int pos, int col) {
	if (l <= pos && pos <= r)
		revise(col, 1), revise(a[pos], -1);
	a[pos] = col;
}

int main() {
	freopen("nt2011_color.in", "r", stdin); 
	freopen("nt2011_color.out", "w", stdout);
	std::cin >> n >> m, t = std::pow(n, 0.6666666);
	for (int i = 1; i <= n; ++ i) 
		std::cin >> a[i], now[i] = a[i], pos[i] = (i - 1) / t + 1;
	while (m --) {
		char op; int x, y;
		std::cin >> op >> x >> y;
		if (op == 'Q') 
			q[++ cnt] = (Q) {x, y, tim, cnt};
		else 
			c[++ tim] = (C) {x, now[x], y}, now[x] = y;
	}
	std::sort(q + 1, q + 1 + cnt, cmp1);
	for (int i = 1; i <= cnt; ++ i) {
		while (T < q[i].tim) 
			++ T, work(c[T].pos, c[T].New);
		while (T > q[i].tim) 
			work(c[T].pos, c[T].Old), -- T;
		while (l < q[i].l) revise(a[l ++], -1);
		while (l > q[i].l) revise(a[-- l],  1);
		while (r < q[i].r) revise(a[++ r],  1);
		while (r > q[i].r) revise(a[r --], -1);
		q[i].ans = ans;
	}
	std::sort(q + 1, q + 1 + cnt, cmp2);
	for (int i = 1; i <= cnt; ++ i)
		std::cout << q[i].ans << '\n';
	return 0;
}