「BZOJ 2120」数颜色

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：BZOJ 2120

墨墨购买了一套 $n​$ 支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：

  • Q l r：询问从第 $l$ 支画笔到第 $r$ 支画笔中共有几种不同颜色的画笔。
  • R p c：把第 $p$ 支画笔替换为颜色 $c$。

数据范围：$1\le n,m\le 5\times 10^4$，$1\le c\le 10^6​$

Solution

由于没有区间可加性，我们考虑带修改莫队。根据「算法笔记」带修改莫队算法 中的分析，我们直接 $O(n^{\frac{2}{3}})$ 分块，然后把询问离线下来，按照套路直接做就行了（Orz 某位叫做 $\color{black}{\text{Q}}\color{red}{\text{Y}}$ 的神仙说可以树套树）。

据说这题分块 + $\text{bitset}​$ 可以卡过去？但是我卡了一个晚上常数还是只有 $80​$ 分啊 QAQ

时间复杂度：$O(n^\frac{5}{3})$

Code

分块

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>

const int N=5e4+5,M=230,C=1e5+5;
int n,m,len,num,a[N],v[N<<1],p[N][3],bl[N],l[M],r[M],cnt[M][C];
std::bitset<C> f[M];

void read(int &t) {
    t=0;char c=getchar();for(;c<'0'||c>'9';c=getchar());
    for(;c>='0'&&c<='9';t=t*10+(c^48),c=getchar());
}
void print(int x) {
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
char getc() {
    char c=getchar();
    while(c!='Q'&&c!='R') c=getchar();
    return c;
}
void build() {
    len=sqrt(n),num=(n-1)/len+1;
    for(int i=1;i<=n;++i) {
        bl[i]=(i-1)/len+1;
        if(++cnt[bl[i]][a[i]]==1) f[bl[i]][a[i]]=1;
    }
    for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
    r[num]=n;
}
void modify(int x,int c) {
    if(--cnt[bl[x]][a[x]]==0) f[bl[x]][a[x]]=0;
    a[x]=c;
    if(++cnt[bl[x]][a[x]]==1) f[bl[x]][a[x]]=1;
}
int query(int x,int y) {
    std::bitset<C> ans;
    if(bl[x]==bl[y]) {
        for(int i=x;i<=y;++i) ans[a[i]]=1;
    } else {
        for(int i=bl[x]+1;i<=bl[y]-1;++i) ans|=f[i];
        for(int i=x;i<=r[bl[x]];++i) ans[a[i]]=1;
        for(int i=l[bl[y]];i<=y;++i) ans[a[i]]=1;
    }
    return ans.count();
}
int main() {
    read(n),read(m);
    int tot=0;
    for(int i=1;i<=n;++i) read(a[i]),v[++tot]=a[i];
    for(int i=1;i<=m;++i) {
        p[i][0]=(getc()=='R');
        read(p[i][1]),read(p[i][2]);
        if(p[i][0]) v[++tot]=p[i][2];
    }
    std::sort(v+1,v+tot+1);
    tot=std::unique(v+1,v+tot+1)-(v+1);
    for(int i=1;i<=n;++i) a[i]=std::lower_bound(v+1,v+tot+1,a[i])-v;
    for(int i=1;i<=m;++i) if(p[i][0]) p[i][2]=std::lower_bound(v+1,v+tot+1,p[i][2])-v;
    build();
    for(int i=1;i<=m;++i) {
        if(p[i][0]) {
            modify(p[i][1],p[i][2]);
        } else {
            print(query(p[i][1],p[i][2])),puts("");
        }
    }
    return 0;
}

莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
 
#include <cstdio>
#include <cmath>
#include <algorithm>

const int N=5e4+5,M=1e6+5;
int n,m,cnt1,cnt2,ret,a[N],b[N],bl[N],cnt[M],ans[N];
struct Data1 {
    int l,r,t,id;
    Data1(int _l=0,int _r=0,int _t=0,int _id=0) {
        l=_l,r=_r,t=_t,id=_id;
    }
    bool operator < (const Data1 &b)const {
        return bl[l]==bl[b.l]?bl[r]==bl[b.r]?t<b.t:r<b.r:l<b.l;
    }
} q[N];
struct Data2 {
    int x,u,v;
    Data2(int _x=0,int _u=0,int _v=0) {
        x=_x,u=_u,v=_v;
    }
} r[N];

void add(int c) {
    if(++cnt[c]==1) ++ret;
}
void del(int c) {
    if(--cnt[c]==0) --ret;
}
void modify(int l,int r,int x,int c) {
    if(l<=x&&x<=r) del(a[x]),add(c);
    a[x]=c;
}
int main() {
    scanf("%d%d",&n,&m);
    int len=pow(n,2.0/3);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),b[i]=a[i],bl[i]=(i-1)/len+1;
    for(int i=1;i<=m;++i) {
        char s[5];
        int x,y;
        scanf("%s%d%d",s,&x,&y);
        if(s[0]=='Q') {
            ++cnt1,q[cnt1]=Data1(x,y,cnt2,cnt1);
        } else {
            r[++cnt2]=Data2(x,b[x],y),b[x]=y;
        }
    }
    std::sort(q+1,q+cnt1+1);
    for(int L=1,R=0,T=0,i=1;i<=cnt1;++i) {
        int x=q[i].l,y=q[i].r,t=q[i].t;
        while(T<t) ++T,modify(L,R,r[T].x,r[T].v);
        while(T>t) modify(L,R,r[T].x,r[T].u),--T;
        while(L<x) del(a[L++]);
        while(L>x) add(a[--L]);
        while(R<y) add(a[++R]);
        while(R>y) del(a[R--]);
        ans[q[i].id]=ret;
    }
    for(int i=1;i<=cnt1;++i) printf("%d\n",ans[i]);
    return 0;
}
0%