思路1：树状数组套主席树
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int N = 1e4 + 5; int a[N], root[N], bitroot[N], head[N*2], lson[N*60], rson[N*60], value[N*60], tot = 0, n; char s[10]; vector<int>vc; set<int>st[N*2]; set<int>::iterator it, pre, nxt; pair<int, pii> Q[N]; void build(int &x, int l, int r) { x = ++tot; if(l == r) { value[x] = 0; return ; } int m = l+r >> 1; build(lson[x], l, m); build(rson[x], m+1, r); value[x] = value[lson[x]] + value[rson[x]]; } void update(int old, int &x, int p, int v, int l, int r) { x = ++tot; lson[x] = lson[old], rson[x] = rson[old], value[x] = value[old] + v; if(l == r) return ; int m = l+r >> 1; if(p <= m) update(lson[x], lson[x], p, v, l, m); else update(rson[x], rson[x], p, v, m+1, r); } int query(int x, int l, int r, int k) { if(l == r) return value[x]; int m = l+r >> 1; if(k <= m) return query(lson[x], l, m, k); else return value[lson[x]] + query(rson[x], m+1, r, k); } void add(int x, int p, int v) { while(x <= n) { update(bitroot[x], bitroot[x], p, v, 0, n); x += x&-x; } } int sum(int x, int k) { int ans = query(root[x], 0, n, k); while(x) { ans += query(bitroot[x], 0, n, k); x -= x&-x; } return ans; } void change(int x, int y) { int now = a[x]; pre = it = nxt = st[now].lower_bound(x); pre--, nxt++; add(x, *pre, -1); if(nxt != st[now].end()) add(*nxt, x, -1), add(*nxt, *pre, 1); st[now].erase(it); a[x] = y; st[y].insert(x); pre = it = nxt = st[y].lower_bound(x); pre--, nxt++; add(x, *pre, 1); if(nxt != st[y].end()) add(*nxt, x, 1), add(*nxt, *pre, -1); } int main() { int m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]), vc.pb(a[i]); for (int i = 1; i <= m; i++) { scanf("%s", s); scanf("%d %d", &Q[i].se.fi, &Q[i].se.se); if(s[0] == 'Q') Q[i].fi = 1; else Q[i].fi = 2, vc.pb(Q[i].se.se); } sort(vc.begin(), vc.end()); vc.erase(unique(vc.begin(), vc.end()), vc.end()); for (int i = 1; i <= n; i++) a[i] = lower_bound(vc.begin(), vc.end(), a[i]) - vc.begin() + 1; for (int i = 1; i <= m; i++) if(Q[i].fi == 2) Q[i].se.se = lower_bound(vc.begin(), vc.end(), Q[i].se.se) - vc.begin() + 1; build(root[0], 0, n); int sz = (int)vc.size(); for (int i = 0; i <= sz; i++) st[i].insert(0); for (int i = 1; i <= n; i++) { update(root[i-1], root[i], head[a[i]], 1, 0, n); head[a[i]] = i; st[a[i]].insert(i); } for (int i = 1; i <= n; i++) bitroot[i] = root[0]; for (int i = 1; i <= m; i++) { if(Q[i].fi == 1) { printf("%d ", sum(Q[i].se.se, Q[i].se.fi -1) - sum(Q[i].se.fi - 1, Q[i].se.fi - 1)); } else { change(Q[i].se.fi, Q[i].se.se); } } return 0; }