[BZOJ 2120][国家集训队2011] 数颜色【带修改莫队】

• 2018-01-28
• 0
• 0

Problem:

Time Limit: 6 Sec  Memory Limit: 259 MB

```6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
```

```4
4
3
4
```

Code: O(QlogQ+N1.5+QN0.5+QT) [5564K, 760MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

inline void getint(int &num){
char ch;
while(!isdigit(ch = getchar()));
num = ch - '0';
while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0';
}

int N, M, a[10005];
int qcnt, mdcnt, bl[10005];
int S[1000005], curans, ans[10005];
char op[5];

struct Query{
int id, l, r, t;

inline bool operator < (const Query &q2) const {
if(bl[l] != bl[q2.l]) return l < q2.l;
if(r != q2.r) return r < q2.r;
return t < q2.t;
}
} q[10005];

struct Modify{
int pos, val;
} md[10005];

inline void Mo_add(int pos) {if(++S[a[pos]] == 1) curans++;}

inline void Mo_del(int pos) {if(--S[a[pos]] == 0) curans--;}

inline void Mo_modify(int t, int id){
if(md[t].pos >= q[id].l && md[t].pos <= q[id].r){
if(--S[a[md[t].pos]] == 0) curans--;
if(++S[md[t].val] == 1) curans++;
}
swap(md[t].val, a[md[t].pos]);
}

inline void Mo_with_modification(){
sort(q + 1, q + qcnt + 1);
for(register int i = 1, l = 1, r = 0, t = 0; i <= qcnt; i++){
while(r > q[i].r) Mo_del(r--);
while(l < q[i].l) Mo_del(l++);
while(t < q[i].t) Mo_modify(++t, i);
while(t > q[i].t) Mo_modify(t--, i);
ans[q[i].id] = curans;
}
}

int main(){
getint(N), getint(M);
for(register int i = 1; i <= N; i++) getint(a[i]);
for(register int i = 1; i <= M; i++){
scanf("%s", op);
if(op[0] == 'Q'){
getint(q[++qcnt].l), getint(q[qcnt].r);
q[qcnt].id = qcnt, q[qcnt].t = mdcnt;
}
else getint(md[++mdcnt].pos), getint(md[mdcnt].val);
}
int blocksize = (int)sqrt(N);
for(register int i = 1; i <= N; i++) bl[i] = (i - 1) / blocksize + 1;
Mo_with_modification();
for(register int i = 1; i <= qcnt; i++) printf("%d\n", ans[i]);
return 0;
}
```

评论

darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai