2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MBSubmit: 3623 Solved: 1396[][][]Description
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令： 1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。 2、 R P Col 把第P支画笔替换为颜色Col。为了满足墨墨的要求，你知道你需要干什么了吗？
Input
第1行两个整数N，M，分别代表初始画笔的数量以及墨墨会做的事情的个数。第2行N个整数，分别代表初始画笔排中第i支画笔的颜色。第3行到第2+M行，每行分别代表墨墨会做的一件事情，格式见题干部分。
Output
对于每一个Query的询问，你需要在对应的行中给出一个数字，代表第L支画笔到第R支画笔中共有几种不同颜色的画笔。
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
Sample Output
4 4 3 4
HINT
对于100%的数据，N≤10000，M≤10000，修改操作不多于1000次，所有的输入数据中出现的所有整数均大于等于1且不超过10^6。
2016.3.2新加数据两组by Nano_Ape
Source
这真是一道好题，貌似有好多种不同的做法。有人用树套树过的，有人用整体二分过的，有人用带修莫队过的，还有像我一样的蒟蒻用常数优化暴力过的。
虽然2016有新加数据，然而依然卡不住暴力，23333。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 1734100 | Accepted | 34496 kb | 2340 ms | / | 1411 B | 2016-12-11 12:45:43 |
1 #include2 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 }
然而不太理解为啥离散化一下就有这么大的用处。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 1734122 | Time_Limit_Exceed | 26684 kb | 7632 ms | / | 1289 B | 2016-12-11 13:00:40 |
1 #include2 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 }
当然，小生来写这道题不是为了练习暴力的，是为了学习带修莫队的。
有别于普通的莫队，带修莫队多了一维对时间的要求，每个询问可以表示为[l,r,t]，表示区间需要我们维护到区间[l,r]在时刻t的存在情况。方法是，对于l,r还按照普通莫队的对l分组方式分组，组内对r排序，转移的时候暴力调整时间即可。貌似为了达到最优秀的复杂度，分组时的大小需要调整一下，但这题显然没有那么苛刻啦，o(*￣▽￣*)ブ
1 #include2 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 }
@Author: YouSiki