1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
|
using namespace std; const int maxn = 1e4 + 5; int n, m; int pos[1000010]; struct { int l, r, t, id; bool operator<(const node &x)const{ return pos[l] ^ pos[x.l] ? l < x.l : (pos[r] ^ pos[x.r] ? r < x.r : t < x.t); } }q[maxn]; typedef pair<int, int> pii; pii c[maxn]; int ans[maxn]; int cntq, cntt, cnt[1000010]; int a[maxn]; int sz; char ch[10]; int main(){ scanf("%d %d", &n, &m); sz = pow(n, 2.0 / 3.0); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= m; i++){ int l, r; scanf("%s %d %d", ch, &l, &r); if(ch[0] == 'Q'){ cntq++; q[cntq].l = l; q[cntq].r = r; q[cntq].id = cntq; q[cntq].t = cntt; } else{ ++cntt; c[cntt].first = l; c[cntt].second = r; } } for(int i = 1; i < 1000010; i++) pos[i] = i / sz; sort(q + 1, q + cntq + 1); int l = 1, r = 0, t = 0; cnt[0] = 1; int res = 0; for(int i = 1; i <= cntq; i++){ while(l < q[i].l) res -= !--cnt[a[l++]]; while(l > q[i].l) res += !cnt[a[--l]]++; while(r < q[i].r) res += !cnt[a[++r]]++; while(r > q[i].r) res -= !--cnt[a[r--]]; while(t < q[i].t){ ++t; if(q[i].l <= c[t].first && c[t].first <= q[i].r) res -= !--cnt[a[c[t].first]] - !cnt[c[t].second]++; swap(a[c[t].first], c[t].second); } while(t > q[i].t){ if(q[i].l <= c[t].first && c[t].first <= q[i].r) res -= !--cnt[a[c[t].first]] - !cnt[c[t].second]++; swap(a[c[t].first], c[t].second); --t; } ans[q[i].id] = res; } for(int i = 1; i <= cntq; i++) printf("%dn", ans[i]); return 0; }
|
近期评论