SDOI2011 染色

发表于
字数统计: 2,571 | 阅读时长 ≈ 14

前言

本来想找一道树剖的题的发现LCT可做…

侵删（博客习惯…

题目

我们来看一道正解为树剖的题目…

题目描述

给定一棵有n个节点的无根树和m个操作，操作有2类：
1、将节点a到节点b路径上所有点都染成颜色c；
2、询问节点a到节点b路径上的颜色段数量（连续相同颜色被认为是同一段），
如“112221”由3段组成：“11”、“222”和“1”。
请你写一个程序依次完成这m个操作。

输入

第一行包含2个整数n和m，分别表示节点数和操作数；
第二行包含n个正整数表示n个节点的初始颜色
下面 行每行包含两个整数x和y，表示x和y之间有一条无向边。
下面 行每行描述一个操作：
“C a b c”表示这是一个染色操作，把节点a到节点b路径上所有点（包括a和b）都染成颜色c；
“Q a b”表示这是一个询问操作，询问节点a到节点b（包括a和b）路径上的颜色段数量。

输出

对于每个询问操作，输出一行答案。

样例输入

6 5
2 2 1 2 1 1
1 2
1 3
2 4
2 5
2 6
Q 3 5
C 2 1 1
Q 3 5
C 5 1 2
Q 3 5

样例输出

3
1
2

提示

数 N<=105，操作数 M <= 105，所有的颜色C为整数且在[ 0 , 109 ]之间。

解题

树链剖分

正解是树剖…

树链剖分解题思路

一道很接近板子的树剖
加上记录一条线段最左边的颜色和最右边的颜色
进行维护 sum 值的时候判断颜色是否相同…
树链剖分虽然代码很长但是跑的比较快的…
是时候展现一波一百六十多行的代码

树链剖分AC代码2008ms
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include<cstdio>  
#include<cstring>  
#include<cmath>  
#include<algorithm>  

using namespace std;  

const int N=100+50;  
const int MAXN=100000+50;  

#define L(x) (x<<1)  
#define R(x) (x<<1|1)  

int n,m,cnt1,cnt,Lc,Rc;  
char str[N];  
int col[MAXN],head[MAXN],sz[MAXN],dep[MAXN],fa[MAXN],son[MAXN],top[MAXN],pos[MAXN];  
struct Edge{  
    int u,v,next;  
}edge[MAXN<<1];  
struct node{  
    int l,r;  
    int num,tag,lc,rc;  
}Tree[MAXN<<2];  

void init(){  
    cnt1=cnt=0;  
    memset(head,-1,sizeof(head));  
}  

void add(int u,int v){  
    edge[cnt1].u=u; edge[cnt1].v=v;  
    edge[cnt1].next=head[u]; head[u]=cnt1++;  
}  

void dfs1(int u,int pre,int depth){  
    sz[u]=1; fa[u]=pre; son[u]=0; dep[u]=depth;  
    for(int i=head[u];i!=-1;i=edge[i].next){  
        int v=edge[i].v;  
        if(v==pre) continue;  
        dfs1(v,u,depth+1);  
        sz[u]+=sz[v];  
        if(sz[son[u]]<sz[v]) son[u]=v;  
    }  
}  

void dfs2(int u,int tp){  
    pos[u]=++cnt;top[u]=tp;  
    if(son[u]!=0) dfs2(son[u],top[u]);  
    for(int i=head[u];i!=-1;i=edge[i].next){  
        int v=edge[i].v;  
        if(v==fa[u]||v==son[u]) continue;  
        dfs2(v,v);  
    }  
}  

void push_down(int rt){  
    if(Tree[rt].tag){  
        Tree[L(rt)].tag=Tree[R(rt)].tag=Tree[rt].tag;  
        Tree[L(rt)].num=Tree[R(rt)].num=1;  
        Tree[L(rt)].lc=Tree[L(rt)].rc=Tree[rt].lc;  
        Tree[R(rt)].lc=Tree[R(rt)].rc=Tree[rt].lc;  
        Tree[rt].tag=0;  
    }  
}  

void push_up(int rt){  
    Tree[rt].lc=Tree[L(rt)].lc; Tree[rt].rc=Tree[R(rt)].rc;  
    int ans=Tree[L(rt)].num+Tree[R(rt)].num;  
    if(Tree[L(rt)].rc==Tree[R(rt)].lc) ans--;  
    Tree[rt].num=ans;  
}  

void build(int rt,int l,int r){  
    Tree[rt].l=l;Tree[rt].r=r;Tree[rt].num=0;  
    if(l==r) return;  
    int mid=(l+r)>>1;
    build(L(rt),l,mid);build(R(rt),mid+1,r);  
}  

void update(int rt,int l,int r,int x){  
    if(Tree[rt].l==l&&Tree[rt].r==r){  
        Tree[rt].num=Tree[rt].tag=1;  
        Tree[rt].lc=Tree[rt].rc=x;  
        return;  
    }  
    push_down(rt);  
    int mid=(Tree[rt].l+Tree[rt].r)>>1;  
    if(r<=mid) update(L(rt),l,r,x);  
    else if(l>mid) update(R(rt),l,r,x);  
    else update(L(rt),l,mid,x),update(R(rt),mid+1,r,x);
    push_up(rt);
}  

int query(int rt,int l,int r,int L,int R){  
    if(Tree[rt].l==L) Lc=Tree[rt].lc;  
    if(Tree[rt].r==R) Rc=Tree[rt].rc;  
    if(Tree[rt].l==l&&Tree[rt].r==r) return Tree[rt].num;
    push_down(rt);
    int mid=(Tree[rt].l+Tree[rt].r)>>1;  
    if(r<=mid) return query(L(rt),l,r,L,R);  
    else if(l>mid) return query(R(rt),l,r,L,R);  
    else{  
        int ans=query(L(rt),l,mid,L,R)+query(R(rt),mid+1,r,L,R);  
        if(Tree[L(rt)].rc==Tree[R(rt)].lc) ans--;
        return ans;
    }
    push_up(rt);
}

int solve(int u,int v,int id,int c){  
    int ans=0;  
    if(id==1){  
        while(top[u]!=top[v]){  
            if(dep[top[u]]<dep[top[v]]) swap(u,v);  
            update(1,pos[top[u]],pos[u],c);  
            u=fa[top[u]];
        }  
        if(dep[u]>dep[v]) swap(u,v);
        update(1,pos[u],pos[v],c);  
    }
    else{
        int ans1=-1,ans2=-1;  
        while(top[u]!=top[v]){  
            if(dep[top[u]]<dep[top[v]]){  
                swap(u,v);swap(ans1,ans2);  
            }  
            ans+=query(1,pos[top[u]],pos[u],pos[top[u]],pos[u]);  
            if(Rc==ans1) ans--;  
            ans1=Lc;u=fa[top[u]];  
        }  
        if(dep[u]<dep[v]){  
            swap(u,v);swap(ans1,ans2);  
        }
        ans+=query(1,pos[v],pos[u],pos[v],pos[u]);  
        if(Rc==ans1) ans--;  
        if(Lc==ans2) ans--;  
    }  
    return ans;  
}  

int main(){
    while(~scanf("%d%d",&n,&m)){  
        init();  
        for(int i=1;i<=n;i++) scanf("%d",&col[i]);  
        for(int i=1;i<n;i++){  
            int u,v;  
            scanf("%d%d",&u,&v);  
            add(u,v);add(v,u);  
        }
        dfs1(1,1,1);dfs2(1,1);build(1,1,n);  
        for(int i=1;i<=n;i++) update(1,pos[i],pos[i],col[i]);  
        while(m--){  
            scanf("%s",str);  
            int u,v;  
            if(str[0] == 'C'){  
                int c;  
                scanf("%d%d%d",&u,&v,&c);  
                solve(u,v,1,c);  
            }  
            else{  
                int u,v;  
                scanf("%d%d",&u,&v);  
                printf("%d\n",solve(u,v,2,0));  
            }  
        }  
    }  
    return 0;  
}

又难打又难修…

LCT

乍一看LCT也能写？！

LCT解题思路

一道很接近模板的LCT，我觉得这道题用来练LCT也是不错的
比一般的模板多出了几个元素需要我们去维护
基本操作是差不多的而且还少了 cut 操作，但是 push_down 与 update 的写法也不太一样需要我们去想
总的来说，我们需要判断一个节点的左儿子最右边的颜色和右儿子最左边的颜色是不是和这个节点相同
所以我们多出的元素就是一条链最左边的颜色和最右边的颜色需要记录
最初的赋值也是要注意的，这次的标记我们不再使用一个而是需要两个了
另外区间翻转的时候不能只翻转左儿子和右儿子，记录的最左边的颜色和最右边的颜色也是需要翻转的
关于上面的判断我觉得代码还是很需要想的毕竟不是那么容易就能实现的
还有一件事我不知道为什么在 link 里把 find（x）==find（y）去掉我就AC否则RE
相较之下LCT代码量虽短但是需要想的东西很多细节也很多代码不容易打好而树剖就比较无脑了…
我开始就以为无脑打LCT就没仔细想 push_down 和 update
所以我们来看一下一百行的LCT…
有什么不会就在代码里找吧

LCT AC代码4740ms
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#define re register int
#define rep(i,a,b) for(re i=(a);i<=(b);++(i))
#define drep(i,a,b) for(re i=(a);i>=(b);--(i))

using namespace std;

inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}

const int N=100010;
int n,m,x,y,z;
char opt;
struct LCT{
    int a[N],fa[N],ch[N][2],lc[N],rc[N],sum[N],tag[N],rev[N],stk[N],top;
    inline bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
    inline void push_down(int x){
        if(tag[x]){
            tag[ch[x][0]]^=1;tag[ch[x][1]]^=1;
            swap(ch[x][0],ch[x][1]);tag[x]=0;
            swap(lc[ch[x][0]],rc[ch[x][0]]);
            swap(lc[ch[x][1]],rc[ch[x][1]]);
        } 
        if(rev[x]){
            lc[x]=rc[x]=a[x]=rev[x];
            rev[ch[x][0]]=rev[ch[x][1]]=rev[x];
            sum[x]=rev[x]=0;
        }
    }
    inline void update(int x){
        push_down(ch[x][0]);push_down(ch[x][1]);
        sum[x]=sum[ch[x][0]]+sum[ch[x][1]];
        if(ch[x][0]){
            lc[x]=lc[ch[x][0]];
            if(a[x]!=rc[ch[x][0]]) sum[x]++; 
        } 
        else lc[x]=a[x];
        if(ch[x][1]){
            rc[x]=rc[ch[x][1]];
            if(a[x]!=lc[ch[x][1]]) sum[x]++;
        }
        else rc[x]=a[x];
    }
    inline void rotate(int x){
        re y=fa[x],z=fa[y],k=ch[y][1]==x;
        if(!isroot(y)) ch[z][ch[z][1]==y]=x;
        fa[x]=z;fa[ch[x][k^1]]=y;ch[y][k]=ch[x][k^1];
        fa[y]=x;ch[x][k^1]=y;update(y);
    }
    inline void splay(int x){
        stk[top=1]=x;for(int i=x;!isroot(i);i=fa[i]) stk[++top]=fa[i];
        drep(i,top,1) push_down(stk[i]); 
        for(re y=fa[x],z=fa[y];!isroot(x);y=fa[x],z=fa[y]){
            if(!isroot(y)) ((ch[y][0]==x)^(ch[z][0]==y))?rotate(x):rotate(y);
            rotate(x);
        }update(x);
    }
    inline int access(int x){
        int t=0;
        while(x){
            splay(x);ch[x][1]=t;t=x;update(x);x=fa[x];
        }
        return t;
    }
    inline void makeroot(int x){
        access(x);splay(x);tag[x]^=1;
    }
    inline void link(int x,int y){
        makeroot(x);fa[x]=y;
    }
}lct;

int main(){
    scanf("%d%d",&n,&m);
    rep(i,1,n) scanf("%d",&lct.a[i]),lct.lc[i]=lct.rc[i]=lct.a[i];
    rep(i,1,n-1) {
        scanf("%d%d",&x,&y);
        lct.link(x,y);
    }
    while(m--){
        opt=getchar();
        while(opt!='C'&&opt!='Q') opt=getchar();
        if(opt=='C'){
            scanf("%d%d%d",&x,&y,&z);
            lct.makeroot(x),lct.access(y);lct.splay(y);
            lct.rev[y]=z;
        }
        if(opt=='Q'){
            scanf("%d%d",&x,&y);
            lct.makeroot(x);lct.access(y);lct.splay(y);
            printf("%d\n",lct.sum[y]+1);
        }
    }
    return 0;
}

后记

事实证明，树剖代码量很大…（接近5K…
但是树剖跑的比LCT快…（2008ms与4740ms
但是我树剖修了好久（代码量太大不容易debug…
一定是我太菜了虽然deLCT的时候也有一些不明不白的锅…
欢迎指正…联系方式如下

qq： 953559040

微博： IncinblePan

洛谷： SherlockPan