**2120: Number of colors**

**Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 8079 Solved: 3321[Submit][Status][Discuss]**

**Description**

**Ink bought a set of N coloured paintbrushes (some of which may be the same color) and put them in a row. You need to answer ink and ink questions. Ink and ink will release the following instructions as you do: 1, Q L R representatives asked you to paint from the L brush to the R brush, there are several different colors of the brush. 2, R PCol replaced the P brush with color Col. Do you know what you need to do to meet ink requirements?**

**Input**

**The first row, two integers N and M, represent the number of initial brushes and the number of things that ink will do. The second line is N integers, representing the color of the I brush in the initial brush row. The third line to line 2+M, each row represents one thing that ink will do, and the format is dry.**

**Output**

**For each Query, you need to give a number in the corresponding line, representing the L brush to the R brush and there are several different colors in the brush.**

**Sample Input**

**6 5**

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

1 2 3 4 5 5

Q 1 4

Q 2 6

R 1 2

Q 1 4

Q 2 6

**Sample Output**

**4**

4

3

4

4

3

4

**HINT**

** **

**For 100% of the data, N is less than 10000, M is less than 10000, and the modified operation is not more than 1000 times. All the integers in all the input data are equal to 1 and not more than 10^6.**

**Summary: to modify the Mo team board**

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 7; typedef long long ll; struct Node{int l, r, tim, ID;} q[N]; struct DATA{int pos, Nw, Od;} c[N]; int t1, t2, sum[N * 10], blo, bl[N]; int n, m, l = 1, r, T, Ans, ans[N], s[N], now[N]; bool cmp(Node a, Node b) { return bl[a.l] == bl[b.l] ?(bl[a.r] == bl[b.r] ?a.tim < b.tim :a.r < b.r) :a.l < b.l; } void revise(int x, int d) { sum[x] += d; (d > 0) ?Ans += sum[x] == 1 :Ans -= sum[x] == 0; } void change(int x, int d) { if(l <= x && x <= r) { revise(d, 1); revise(s[x], -1); } s[x] = d; } int main() { char ch[2]; scanf("%d%d", &n, &m); blo = sqrt(n); for (int i = 1; i <= n; ++i) scanf("%d", &s[i]), now[i] = s[i], bl[i] = i / blo + 1; for (int i = 1; i <= m; ++i) { int x, y; scanf("%s%d%d", ch, &x, &y); if(ch[0] == 'Q') q[++t1] = (Node) {x, y, t2, t1}; else c[++t2] = (DATA) {x, y, now[x]}, now[x] = y; } sort(q + 1, q + t1 + 1, cmp); for (int i = 1; i <= t1; ++i) { while(T < q[i].tim) change(c[T + 1].pos, c[T + 1].Nw), ++T; while(T > q[i].tim) change(c[T].pos, c[T].Od), --T; while(l < q[i].l) revise(s[l++], -1); while(l > q[i].l) revise(s[--l], 1); while(r < q[i].r) revise(s[++r], 1); while(r > q[i].r) revise(s[r--], -1); ans[q[i].ID] = Ans; } for (int i = 1; i <= t1; ++i) printf("%d\n", ans[i]); return 0; }