墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？

第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。

对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。

对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。

2016.3.2新加数据两组by Nano_Ape

 1 #include <bits/stdc++.h> 2  3 const int siz = 10000000; 4  5 char buf[siz], *bit = buf; 6  7 inline int nextInt (void) { 8     register int ret = 0; 9     register int neg = 0;10     11     while (*bit < ‘0‘)12         if (*bit++ == ‘-‘)13             neg ^= true;14     15     while (*bit >= ‘0‘)16         ret = ret*10 + *bit++ - ‘0‘;17         18     return neg ? -ret : ret;19 }20 21 inline char nextChar (void) {22     while (*bit != ‘Q‘ && *bit != ‘R‘)++bit;23     return *bit ++;24 }25 26 const int maxn = 2000000 + 5;27 28 int n, m;29 int cases;30 int total;31 int answer;32 int col[maxn];33 int map[maxn];34 int vis[maxn];35 36 signed main (void) {37     fread (buf, 1, siz, stdin);38     39     n = nextInt ();40     m = nextInt ();41     42     for (register int i = 1; i <= n; ++i) {43         int color = nextInt ();44         if (map[color] == 0)45             map[color] = ++total;46         col[i] = map[color];47     }48     49     for (register int i = 1; i <= n; ++i) {50         switch (nextChar ()) {51             case ‘R‘ : {52                 int a = nextInt ();53                 int b = nextInt ();54                 if (map[b] == 0)55                     map[b] = ++total;56                 col[a] = map[b];57                 break;58             }59             case ‘Q‘ : {60                 int a = nextInt ();61                 int b = nextInt ();62                 answer = 0, ++cases;63                 for (register int j = a; j <= b; ++j)64                     if (vis[col[j]] != cases)++answer, vis[col[j]] = cases;65                 printf("%d\n", answer);66             }67         }68     }69 }

 1 #include <bits/stdc++.h> 2  3 const int siz = 10000000; 4  5 char buf[siz], *bit = buf; 6  7 inline int nextInt (void) { 8     register int ret = 0; 9     register int neg = 0;10     11     while (*bit < ‘0‘)12         if (*bit++ == ‘-‘)13             neg ^= true;14     15     while (*bit >= ‘0‘)16         ret = ret*10 + *bit++ - ‘0‘;17         18     return neg ? -ret : ret;19 }20 21 inline char nextChar (void) {22     while (*bit != ‘Q‘ && *bit != ‘R‘)++bit;23     return *bit ++;24 }25 26 const int maxn = 2000000 + 5;27 28 int n, m;29 int cases;30 int answer;31 int col[maxn];32 int vis[maxn];33 34 signed main (void) {35     fread (buf, 1, siz, stdin);36     37     n = nextInt ();38     m = nextInt ();39     40     for (register int i = 1; i <= n; ++i)41         col[i] = nextInt ();42         43     for (register int i = 1; i <= m; ++i) {44         switch (nextChar ()) {45             case ‘R‘ : {46                 int a = nextInt ();47                 int b = nextInt ();48                 col[a] = b;49                 break;50             }51             case ‘Q‘ : {52                 int a = nextInt ();53                 int b = nextInt ();54                 answer = 0, ++cases;55                 for (register int j = a; j <= b; ++j)56                     if (vis[col[j]] != cases)++answer, vis[col[j]] = cases;57                 printf ("%d\n", answer);58             }59         }60     }61 }

  1 #include <bits/stdc++.h>  2   3 const int siz = 10000000;  4   5 char buf[siz], *bit = buf;  6   7 inline int nextInt (void) {  8     register int ret = 0;  9     register int neg = 0; 10      11     while (*bit < ‘0‘) 12         if (*bit++ == ‘-‘) 13             neg ^= true; 14      15     while (*bit >= ‘0‘) 16         ret = ret*10 + *bit++ - ‘0‘; 17          18     return neg ? -ret : ret; 19 } 20  21 inline char nextChar (void) { 22     while (*bit != ‘Q‘ && *bit != ‘R‘)++bit; 23     return *bit ++; 24 } 25  26 const int maxn = 200000 + 5; 27 const int maxm = 2000000 + 5; 28  29 int n, m; 30 int l, r; 31 int s, t; 32 int answer; 33 int col[maxn]; 34 int vis[maxm]; 35  36 struct query { 37     int l, r, id, ans; 38 }qry[maxn]; int q; 39  40 struct change { 41     int p, a, b, id; 42 }chg[maxn]; int c; 43  44 inline bool cmp_lr (const query &A, const query &B) { 45     if (A.l / s != B.l / s) 46         return A.l < B.l; 47     else 48         return A.r < B.r; 49 } 50  51 inline bool cmp_id (const query &A, const query &B) { 52     return A.id < B.id; 53 } 54  55 inline void removeColor (int c) { 56     if (--vis[c] == 0)--answer; 57 } 58  59 inline void insertColor (int c) { 60     if (++vis[c] == 1)++answer; 61 } 62  63 inline void removeChange (change &c) { 64     col[c.p] = c.a; 65     if (c.p >= l && c.p <= r) { 66         removeColor(c.b); 67         insertColor(c.a); 68     } 69 } 70  71 inline void insertChange (change &c) { 72     col[c.p] = c.b; 73     if (c.p >= l && c.p <= r) { 74         removeColor(c.a); 75         insertColor(c.b); 76     } 77 } 78  79 inline void solve (query &q) { 80     while (t > 0 && chg[t].id > q.id) 81         removeChange (chg[t--]); 82     while (t < c && chg[t + 1].id < q.id) 83         insertChange (chg[++t]); 84          85      86          87     while (l < q.l)removeColor (col[l++]); 88     while (l > q.l)insertColor (col[--l]); 89     while (r < q.r)insertColor (col[++r]); 90     while (r > q.r)removeColor (col[r--]); 91      92     q.ans = answer; 93 } 94  95 signed main (void) { 96     fread (buf, 1, siz, stdin); 97      98     n = nextInt (); 99     m = nextInt ();100     101     for (register int i = 1; i <= n; ++i)102         col[i] = nextInt ();103         104     for (register int i = 1; i <= m; ++i) {105         switch (nextChar ()) {106             case ‘R‘ : {107                 chg[++c].id = i;108                 chg[c].p = nextInt ();109                 chg[c].b = nextInt ();110                 chg[c].a = col[chg[c].p];111                 col[chg[c].p] = chg[c].b;112                 break;113             }114             case ‘Q‘ : {115                 qry[++q].id = i;116                 qry[q].l = nextInt ();117                 qry[q].r = nextInt ();118             }119         }120     }121     122     s = sqrt (n); t = c; answer = 0; l = 1; r = 0;123     124     std::sort (qry + 1, qry + 1 + q, cmp_lr);125     126     for (register int i = 1; i <= q; ++i)solve(qry[i]);127     128     std::sort (qry + 1, qry + 1 + q, cmp_id);129     130     for (register int i = 1; i <= q; ++i)131         printf ("%d\n", qry[i].ans);132 }