#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
const int N = 1e6 + 10;
int n, m, a[N], ans[N], qcnt, updcnt;
struct QUESTION {
    int l, r, k, id, t;
} q[N];
struct UPDATE {
    int p, x;
} upd[N];
struct INIT {
    int id1, id2, v;
    friend bool operator<(const INIT &a, const INIT &b) {
        return a.v < b.v;
    }
} b[N];

namespace MoDui {
    int block, belong[N];
    int cnt[N];
    void init_block() {
        block = pow(n, 2.0 / 3);
        for (int i = 1; i <= n; i++) belong[i] = (i - 1) / block + 1;
    }
    bool cmp(QUESTION x, QUESTION y) {
        if (belong[x.l] != belong[y.l]) return x.l < y.l;
        if (belong[x.r] != belong[y.r]) return x.r < y.r;
        return x.t < y.t;
    }
    void add(int x) { cnt[x]++; }
    void del(int x) { cnt[x]--; }
    void update(int t, int x) {
        if (q[x].l <= upd[t].p and upd[t].p <= q[x].r) {
            add(upd[t].x);
            del(a[upd[t].p]);
        }
        swap(upd[t].x, a[upd[t].p]);
    }
    void solve() {
        sort(q + 1, q + qcnt + 1, cmp);
        int l = 1, r = 0, t = 0;
        for (int i = 1; i <= qcnt; i++) {
            while (l > q[i].l) add(a[--l]);
            while (l < q[i].l) del(a[l++]);
            while (r < q[i].r) add(a[++r]);
            while (r > q[i].r) del(a[r--]);
            while (t < q[i].t) update(++t, i);
            while (t > q[i].t) update(t--, i);
            ans[q[i].id] = cnt[q[i].k];
        }
    }
}
using namespace MoDui;

void init_() {
    int cnt = 0, tmp = 0;
    for (int i = 1; i <= n; i++) b[++cnt] = {1, i, a[i]};
    for (int i = 1; i <= updcnt; i++) b[++cnt] = {2, i, upd[i].x};
    for (int i = 1; i <= qcnt; i++) b[++cnt] = {3, i, q[i].k};
    sort(b + 1, b + cnt + 1);
    for (int i = 1; i <= cnt; i++) {
        if (b[i].v != b[i - 1].v) tmp++;
        if (b[i].id1 == 1) a[b[i].id2] = tmp;
        else if (b[i].id1 == 2) upd[b[i].id2].x = tmp;
        else q[b[i].id2].k = tmp;
    }
}

signed main() {
    IOS;
    cin >> n >> m;
    init_block();
    for (int i = 1; i <= n; i++) cin >> a[i];
    init_();
    for (int i = 1; i <= m; i++) {
        char opt;
        int x, y, k;
        cin >> opt >> x >> y;
        if (opt == 'Q') {
            cin >> k;
            q[++qcnt] = {x, y, k, qcnt, updcnt};
        } else if (opt == 'C') upd[++updcnt] = {x, y};
    }
    solve();
    for (int i = 1; i <= qcnt; i++) cout << ans[i] << "\n";
    return 0;
}