带修莫队。那是什么。能吃吗。
我们可以把区间数颜色转化为二维数点，带修就是动态二位数点，即三维数点。
然后随便做了。
#include <bits/stdc++.h>
#define llong long long
#define N 4000006
using namespace std;#define bs (1<<20)
char buf[bs], *p1, *p2;
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,bs,stdin),p1==p2)?EOF:*p1++)
template<typename T>
inline void read(T& x){x = 0; int w = 1;char ch = gc();while(ch < '0' || ch > '9'){if(ch == '-') w = -w;ch = gc();}while(ch >= '0' && ch <= '9')x = (x<<3)+(x<<1)+(ch^48), ch = gc();x *= w;
}
inline void read(char& ch){ch = gc();while(ch == ' ' || ch == '\r' || ch == '\n') ch = gc();
}
template<typename T, typename ...Args>
inline void read(T& x, Args& ...y){return read(x), read(y...);
}int n, q, cnt, qcnt;
int b[N];
struct Node{int t, x, y, w;int id;
} a[N];
int ans[N];set<int> col[N];int fwk[N];
#define lowbit(x) (x&-x)
inline void modify(int x, int k){for(int i = x; i < N; i += lowbit(i)) fwk[i] += k;}
inline int query(int x){int res = 0; for(int i = x; i; i ^= lowbit(i)) res += fwk[i]; return res;}
inline void clear(int x){for(int i = x; i < N; i += lowbit(i)) fwk[i] = 0;}#define mid ((l+r)>>1)
inline void cdq(int l, int r){if(l == r) return;cdq(l, mid), cdq(mid+1, r);sort(a+l, a+mid+1, [&](Node o1, Node o2){return o1.x<o2.x;});sort(a+mid+1, a+r+1, [&](Node o1, Node o2){return o1.x<o2.x;});int i = l, j = mid+1;while(j <= r){while(i <= mid && a[i].x <= a[j].x){if(!a[i].id) modify(a[i].y, a[i].w);++i;}if(a[j].id) ans[a[j].id] += query(a[j].y)*a[j].w;++j;}for(int k = l; k < i; ++k)if(!a[k].id) clear(a[k].y);return;
}int main(){freopen("in.txt", "r", stdin);read(n, q);for(int i = 1; i <= n; ++i) read(b[i]);for(int i = n; i >= 1; --i){a[++cnt] = {0, i, i, 1, 0};auto it = col[b[i]].upper_bound(i);if(it != col[b[i]].end()){int pos = *it;a[++cnt] = {0, pos, i, -1, 0};}col[b[i]].insert(i);}for(int i = 1; i <= q; ++i){char op; int x, y;read(op, x, y);if(op == 'R'){// Eraseint pos1 = 0, pos2 = 0;set<int>::iterator it1, it2;it1 = it2 = col[b[x]].lower_bound(x);if(it1 != col[b[x]].begin()) pos1 = *--it1;if(++it2 != col[b[x]].end()) pos2 = *it2;if(pos1) a[++cnt] = {i, pos1, x, 1, 0};if(pos2) a[++cnt] = {i, x, pos2, 1, 0};if(pos1 && pos2) a[++cnt] = {i, pos1, pos2, -1, 0};col[b[x]].erase(x);// Insertb[x] = y, pos1 = pos2 = 0;it1 = it2 = col[b[x]].lower_bound(x);if(it1 != col[b[x]].begin()) pos1 = *--it1;if(it2 != col[b[x]].end()) pos2 = *it2;if(pos1) a[++cnt] = {i, pos1, x, -1, 0};if(pos2) a[++cnt] = {i, x, pos2, -1, 0};if(pos1 && pos2) a[++cnt] = {i, pos1, pos2, 1, 0};col[b[x]].insert(x);}if(op == 'Q'){++qcnt;a[++cnt] = {i, y, y, 1, qcnt};if(x == 1) continue;a[++cnt] = {i, x-1, y, -1, qcnt};a[++cnt] = {i, y, x-1, -1, qcnt};a[++cnt] = {i, x-1, x-1, 1, qcnt};}}sort(a+1, a+cnt+1, [&](Node o1, Node o2){return o1.t<o2.t || (o1.t==o2.t&&(o1.x<o2.x||(o1.x==o2.x&&(o1.y<o2.y||(o1.y==o2.y&&o1.id<o2.id)))));});cdq(1, cnt);for(int i = 1; i <= qcnt; ++i) printf("%d\n", ans[i]);return 0;
}