2120: 数颜色
Time Limit: 6 Sec Memory Limit: 259 MB
Submit: 3623 Solved: 1396
[Submit][Status][Discuss]
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
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
对于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 | YOUSIKI | 2120 | Accepted | 34496 kb | 2340 ms | C++/Edit | 1411 B | 2016-12-11 12:45:43 |
#include <bits/stdc++.h>
const int siz = ;
char buf[siz], *bit = buf;
inline int nextInt (void) {
register int ret = ;
register int neg = ;
while (*bit < '')
if (*bit++ == '-')
neg ^= true;
while (*bit >= '')
ret = ret* + *bit++ - '';
return neg ? -ret : ret;
}
inline char nextChar (void) {
while (*bit != 'Q' && *bit != 'R')++bit;
return *bit ++;
}
const int maxn = + ;
int n, m;
int cases;
int total;
int answer;
int col[maxn];
int map[maxn];
int vis[maxn];
signed main (void) {
fread (buf, , siz, stdin);
n = nextInt ();
m = nextInt ();
for (register int i = ; i <= n; ++i) {
int color = nextInt ();
if (map[color] == )
map[color] = ++total;
col[i] = map[color];
}
for (register int i = ; i <= n; ++i) {
switch (nextChar ()) {
case 'R' : {
int a = nextInt ();
int b = nextInt ();
if (map[b] == )
map[b] = ++total;
col[a] = map[b];
break;
}
case 'Q' : {
int a = nextInt ();
int b = nextInt ();
answer = , ++cases;
for (register int j = a; j <= b; ++j)
if (vis[col[j]] != cases)++answer, vis[col[j]] = cases;
printf("%d\n", answer);
}
}
}
}
然而不太理解为啥离散化一下就有这么大的用处。
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 1734122 | YOUSIKI | 2120 | Time_Limit_Exceed | 26684 kb | 7632 ms | C++/Edit | 1289 B | 2016-12-11 13:00:40 |
#include <bits/stdc++.h>
const int siz = ;
char buf[siz], *bit = buf;
inline int nextInt (void) {
register int ret = ;
register int neg = ;
while (*bit < '')
if (*bit++ == '-')
neg ^= true;
while (*bit >= '')
ret = ret* + *bit++ - '';
return neg ? -ret : ret;
}
inline char nextChar (void) {
while (*bit != 'Q' && *bit != 'R')++bit;
return *bit ++;
}
const int maxn = + ;
int n, m;
int cases;
int answer;
int col[maxn];
int vis[maxn];
signed main (void) {
fread (buf, , siz, stdin);
n = nextInt ();
m = nextInt ();
for (register int i = ; i <= n; ++i)
col[i] = nextInt ();
for (register int i = ; i <= m; ++i) {
switch (nextChar ()) {
case 'R' : {
int a = nextInt ();
int b = nextInt ();
col[a] = b;
break;
}
case 'Q' : {
int a = nextInt ();
int b = nextInt ();
answer = , ++cases;
for (register int j = a; j <= b; ++j)
if (vis[col[j]] != cases)++answer, vis[col[j]] = cases;
printf ("%d\n", answer);
}
}
}
}
当然，小生来写这道题不是为了练习暴力的，是为了学习带修莫队的。
有别于普通的莫队，带修莫队多了一维对时间的要求，每个询问可以表示为[l,r,t]，表示区间需要我们维护到区间[l,r]在时刻t的存在情况。方法是，对于l,r还按照普通莫队的对l分组方式分组，组内对r排序，转移的时候暴力调整时间即可。貌似为了达到最优秀的复杂度，分组时的大小需要调整一下，但这题显然没有那么苛刻啦，o(*￣▽￣*)ブ
#include <bits/stdc++.h>
const int siz = ;
char buf[siz], *bit = buf;
inline int nextInt (void) {
register int ret = ;
register int neg = ;
while (*bit < '')
if (*bit++ == '-')
neg ^= true;
while (*bit >= '')
ret = ret* + *bit++ - '';
return neg ? -ret : ret;
}
inline char nextChar (void) {
while (*bit != 'Q' && *bit != 'R')++bit;
return *bit ++;
}
const int maxn = + ;
const int maxm = + ;
int n, m;
int l, r;
int s, t;
int answer;
int col[maxn];
int vis[maxm];
struct query {
int l, r, id, ans;
}qry[maxn]; int q;
struct change {
int p, a, b, id;
}chg[maxn]; int c;
inline bool cmp_lr (const query &A, const query &B) {
if (A.l / s != B.l / s)
return A.l < B.l;
else
return A.r < B.r;
}
inline bool cmp_id (const query &A, const query &B) {
return A.id < B.id;
}
inline void removeColor (int c) {
if (--vis[c] == )--answer;
}
inline void insertColor (int c) {
if (++vis[c] == )++answer;
}
inline void removeChange (change &c) {
col[c.p] = c.a;
if (c.p >= l && c.p <= r) {
removeColor(c.b);
insertColor(c.a);
}
}
inline void insertChange (change &c) {
col[c.p] = c.b;
if (c.p >= l && c.p <= r) {
removeColor(c.a);
insertColor(c.b);
}
}
inline void solve (query &q) {
while (t > && chg[t].id > q.id)
removeChange (chg[t--]);
while (t < c && chg[t + ].id < q.id)
insertChange (chg[++t]);
while (l < q.l)removeColor (col[l++]);
while (l > q.l)insertColor (col[--l]);
while (r < q.r)insertColor (col[++r]);
while (r > q.r)removeColor (col[r--]);
q.ans = answer;
}
signed main (void) {
fread (buf, , siz, stdin);
n = nextInt ();
m = nextInt ();
for (register int i = ; i <= n; ++i)
col[i] = nextInt ();
for (register int i = ; i <= m; ++i) {
switch (nextChar ()) {
case 'R' : {
chg[++c].id = i;
chg[c].p = nextInt ();
chg[c].b = nextInt ();
chg[c].a = col[chg[c].p];
col[chg[c].p] = chg[c].b;
break;
}
case 'Q' : {
qry[++q].id = i;
qry[q].l = nextInt ();
qry[q].r = nextInt ();
}
}
}
s = sqrt (n); t = c; answer = ; l = ; r = ;
std::sort (qry + , qry + + q, cmp_lr);
for (register int i = ; i <= q; ++i)solve(qry[i]);
std::sort (qry + , qry + + q, cmp_id);
for (register int i = ; i <= q; ++i)
printf ("%d\n", qry[i].ans);
}
@Author: YouSiki