带修莫队求调

#include<bits/stdc++.h>

using namespace std;

#define Reimu inline void // 灵梦赛高
#define Marisa inline int // 魔理沙赛高
#define Sanae inline bool // 早苗赛高

typedef long long LL;
typedef unsigned long long ULL;

typedef pair<int, int> Pii;
typedef tuple<int, int, int> Tiii;
#define fi first
#define se second

namespace FastInput {
	template<typename Ty>
	Reimu read(Ty &x) { // 默认读入整型 int, LL, Uint, ULL, ...
		x = 0;
		int f = 0;
		char c = getchar();
		for (; !isdigit(c); c = getchar()) f |= c == '-';
		for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
		if (f) x = -x;
	}

	template<>
	Reimu read(double &x) { // 读入浮点型 double
		x = 0;
		int f = 0;
		char c = getchar();
		for (; !isdigit(c); c = getchar()) f |= c == '-';
		for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
		if (c == '.') {
			double e = 1;
			for (c = getchar(); isdigit(c); c = getchar()) x += (c ^ 48) * (e *= .1);
		}
		if (f) x = -x;
	}

	template<>
	Reimu read(char &c) { // 读入字符 char
		do c = getchar(); while (!isgraph(c));
	}

	template<>
	Reimu read(string &s) { // 读入字符串 string
		s = "";
		char c = getchar();
		while (!isgraph(c)) c = getchar();
		for (; isgraph(c); c = getchar()) s += c;
	}

	template<typename Ty, typename...Args>
	Reimu read(Ty &x, Args &...args) { // 不定长传参
		read(x);
		read(args...);
	}
}
using namespace FastInput; // 使用快读

const int N = 150010;

struct Que { int l, r, ti, k; } q[N];

int n, m, qC, answer;
int col[N], loc[N], oth[N], ans[N], c[N];

Reimu add(int x) { answer += !c[x]++; }
Reimu del(int x) { answer -= !--c[x]; }
Reimu mov(int x, int i) { if (x >= q[i].l && x <= q[i].r) { del(col[loc[x]]); add(oth[x]); } swap(col[loc[x]], oth[x]); }

Reimu solve() {
	sort(q + 1, q + qC + 1, [](Que a, Que b) { return a.l < b.l; });
	int len1 = pow(qC, 2. / 3), c1 = (qC - 1) / len1 + 1;
	for (int i = 1; i <= c1; ++i) {
		int l1 = len1 * (i - 1) + 1, r1 = i == c1 ? qC : len1 * i;
		sort(q + l1, q + r1 + 1, [](Que a, Que b) { return a.r < b.r; });
		int len2 = sqrt(r1 - l1 + 1), c2 = (r1 - l1) / len2 + 1;
		for (int j = 1; j <= c2; ++j) {
			int l2 = l1 + len2 * (j - 1), r2 = j == c2 ? r1 : l1 + len2 * j - 1;
			sort(q + l2, q + r2 + 1, [](Que a, Que b) { return a.ti < b.ti; });
		}
	}
	for (int i = 1, l = 1, r = 0, ti = 0; i <= qC; ++i) {
		while (r < q[i].r) add(col[++r]);
		while (l > q[i].l) add(col[--l]);
		while (r > q[i].r) del(col[r--]);
		while (l < q[i].l) del(col[l++]);
		while (ti < q[i].ti) mov(++ti, i);
		while (ti > q[i].ti) mov(ti--, i);
		ans[q[i].k] = answer;
	}
}

int main() {
	read(n, m);
	for (int i = 1; i <= n; ++i) read(col[i]);
	for (int i = 1, ti = 0, x, y; i <= m; ++i) {
		char c; read(c, x, y);
		if (c == 'Q') q[++qC] = {x, y, ti, qC};
		else {
			++ti;
			loc[ti] = x;
			oth[ti] = y;
		}
	}
	solve();
	for (int i = 1; i <= qC; ++i) printf("%d\n", ans[i]);
	return 0;
}