```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
const int V = 2e5 + 5;
int cnt[V], a[N], ans[N];
int n, m, cntq, cntr, cur, siz;
vector<int> pool;
struct node{
int l, r, t, bel, id, q;
bool operator < (const node & o) const {
if(l / siz == o.l / siz){
if(r / siz == o.r /siz) return t < o.t;
else if(l / siz & 1) return r > o.r; else return r < o.r;
}
else return l< o.l;
}
}qq[N],qr[N];
inline void add(int i){
cnt[i]++;
}
inline void del(int i){
cnt[i]--;
}
inline void update(int i,int t){
if(qq[i].l <= qr[t].l && qr[t].l <= qq[i].r){
del(a[qr[t].l]);
add(qr[t].r);
}
swap(a[qr[t].l], qr[t].r);
}
int main(){
// freopen("librarian.in","r",stdin);
// freopen("librarian.out","w",stdout);
scanf("%d %d", &n, &m);
siz = pow(n,0.66);
for(int i = 1; i <= n ; i++) scanf("%d", &a[i]), pool.push_back(a[i]);
for(int i = 1; i <= m ; i++){
char op[5];
int l, r;
scanf("%s%d%d",op,&l,&r);
if(op[0] == 'Q'){
int q;
scanf("%d", &q);
qq[++cntq].l = l;
qq[cntq].r = r;
qq[cntq].id = cntq;
qq[cntq].t =cntr;
qq[cntq].q = q;
pool.push_back(q);
}
else {
pool.push_back(r);
qr[++cntr].l = l;
qr[cntr].r = r;
}
}
int l = 1, r = 0, t = 0;
sort(pool.begin(), pool.end());
pool.erase(unique(pool.begin(), pool.end()), pool.end());
for(int i = 1; i <= n; i++) a[i] = lower_bound(pool.begin(), pool.end(), a[i]) - pool.begin();;
for(int i = 1; i <= cntr; i++) qr[i].r = lower_bound(pool.begin(), pool.end(), qr[i].r) - pool.begin();
for(int i = 1; i <= cntq; i++) qq[i].q = lower_bound(pool.begin(), pool.end(), qq[i].q) - pool.begin();
sort(qq + 1 , qq + 1 + cntq);
for(int i = 1; i <= cntq; i++){
while(l < qq[i].l) del(a[l++]);
while(l > qq[i].l) add(a[--l]);
while(r < qq[i].r) add(a[++r]);
while(r > qq[i].r) del(a[r--]);
while(t < qq[i].t) update(i, ++t);
while(t > qq[i].t) update(i, t--);
ans[qq[i].id] = cnt[qq[i].q];
}
for(int i = 1; i <= cntq; i++) printf("%d\n",ans[i]);
}
by CQBZ_CHECK @ 2024-01-29 14:22:18
thanks
by midsummer_zyl @ 2024-01-29 14:33:18