[BZOJ 1483] 梦幻布丁

Posted on | Edited on | In , | Views:

题目链接

BZOJ 1483

题目大意

有一个长为n的的数列，数列上每个点有个颜色，有m此操作，每次操作可以将一种颜色的所有点染成另一种颜色，或这查询当前有几段颜色。
$n,m\le1000000$

做法

网上好多的做法都是链表合并，我感觉有点难写，这里提供一种不一样的思路，线段树合并，复杂度是一样的，都是一个log，但是代码复杂度应该会比较简单。
我们对每个颜色建一棵线段树，线段树每个节点记录三个信息，size，ll，rr，分别表示这个颜色这段区间中的段数，左边是否顶到，右边是否顶到。
update的时候，

1
size[u]=size[lson[u]+size[rson]-(rr[lson[u]&&ll[rson[u])

应该可以理解吧。
那么一开始的答案就是所有size[root[i]]的和。
对于修改操作，我们先

1
ans-=size[root[x]]+size[root[y]]

然后我们把x的这棵线段树合并到y上面，因为底层的节点不会重复，所以我们先递归到底层，然后不断update上来就行了，这里的合并使用启发式合并，保证复杂度的正确性。最后ans在加上size[root[y]]就行了，然后记得把root[x]设为0。
注意判一下x==y的情况就行了。

代码

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
71
72
73
74
75
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
#define N (100005)
#define M (1000005)
using namespace std;
int n,m,cnt,ans,op,x,y;
int a[N],tot[M],root[M],lson[N*21],rson[N*21],size[N*21];
bool ll[N*21],rr[N*21];
template <typename T> void read(T&t) {
    t=0;
    bool fl=true;
    char p=getchar();
    while (!isdigit(p)) {
        if (p=='-') fl=false;
        p=getchar();
    }
    do {
        (t*=10)+=p-48;p=getchar();
    }while (isdigit(p));
    if (!fl) t=-t;
}
void update(int u){
    ll[u]=ll[lson[u]],rr[u]=rr[rson[u]];
    size[u]=size[lson[u]]+size[rson[u]]-(rr[lson[u]]&&ll[rson[u]]);
}
void insert(int &u,int l,int r,int op){
    if (!u) u=++cnt;
    if (l==r){
        ll[u]=rr[u]=1;
        size[u]=1;
        return;
    }
    int mid=l+r>>1;
    if (op<=mid) insert(lson[u],l,mid,op);
    else insert(rson[u],mid+1,r,op);
    update(u);
}
void merge(int &x,int y){
    if (!x||!y){
        x|=y;
        return;
    }
    merge(lson[x],lson[y]);
    merge(rson[x],rson[y]);
    update(x);
}
int main(){
    read(n),read(m);
    for (int i=1;i<=n;i++){
        read(a[i]);
        tot[a[i]]++;
        insert(root[a[i]],1,n,i);
    }
    for (int i=1;i<=1000000;i++) ans+=size[root[i]];
    while (m--){
        read(op);
        if (op==2){
            printf("%d\n",ans); 
        }
        if (op==1){
            read(x),read(y);
            if (x==y) continue;
            ans-=size[root[x]]+size[root[y]];
            merge(root[y],root[x]);
            ans+=size[root[y]];
            root[x]=0;
        }
    }
    return 0;
}