```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int n, m, r, q, tot;
int val[N], ans[N], len, bel[N], cnt[N];
//书的编码 | 答案 | 块长 | 对应块 | 编码本数
vector<int> all; //离散化数组
struct Change{ //存储修改操作
int x, v;
//位置,值
} C[N];
struct Query{ //存储查询操作
int l, r, t, k, id;
//左、右端点,时刻,值,顺序
} Q[N];
bool cmp(Query x, Query y) { //带修莫队，对左右端点都分了块
return (bel[x.l] == bel[y.l]) ? ((bel[x.r] == bel[y.r]) ?
x.t < y.t : x.r < y.r) : x.l < y.l;
}
int main() {
scanf("%d%d", &n, &m); len = sqrt(n);
for (int i = 1; i <= n; i ++) {
scanf("%d", &val[i]);
bel[i] = (i-1) / len + 1;
all.push_back(val[i]);
}
for (int i = 1; i <= m; i ++) {
char op[2];
int a, b, k;
scanf("%s%d%d", &op, &a, &b);
if (op[0] == 'C')
C[++ r] = {a, b},
all.push_back(b);
else {
scanf("%d", &k);
Q[++ q] = {a, b, r, k, q};
all.push_back(k);
}
}
//输入
sort(all.begin(), all.end());
tot = unique(all.begin(), all.end()) - all.begin();
for (int i = 1; i <= n; i ++)
val[i] = lower_bound(all.begin(), all.end(), val[i]) - all.begin();
for (int i = 1; i <= r; i ++)
C[i].v = lower_bound(all.begin(), all.end(), C[i].v) - all.begin();
for (int i = 1; i <= q; i ++)
Q[i].k = lower_bound(all.begin(), all.end(), Q[i].k) - all.begin();
sort(Q+1, Q+q+1, cmp);
//离散化
int l = 1, r = 0, t = 0;
//左指针、右指针、时间点
for (int i = 1; i <= q; i ++) {
int L = Q[i].l, R = Q[i].r, T = Q[i].t;
while (l > L) cnt[val[-- l]] ++;
while (r < R) cnt[val[++ r]] ++;
while (l < L) cnt[val[l ++]] --;
while (r > R) cnt[val[r --]] --;
while (t < T) {
++ t;
if (C[t].x <= R && C[t].x >= L)
cnt[val[C[t].x]] --, cnt[C[t].v] ++;
swap(val[C[t].x], C[t].v);
}
while (t > T) {
if (C[t].x <= R && C[t].x >= L)
cnt[val[C[t].x]] --, cnt[C[t].v] ++;
swap(val[C[t].x], C[t].v);
t --;
}
ans[Q[i].id] = cnt[Q[i].k];
}
//莫队
for (int i = 1; i <= q; i ++) printf("%d\n", ans[i]);
//输出
}
```
by Arson1st @ 2023-10-18 10:58:22
更新：将块长调为 $n^{\frac{2}{3}}$ 后可做到无氧90pts，吸氧AC……不知道还有什么地方可以再优化了
by Arson1st @ 2023-10-18 11:20:59