1
9
2014
0

LCT专题

 LCT，传说中的动态树，写得我蛋疼啊。

【BZOJ2002】【hnoi2012】弹飞绵羊

裸LCT，只需要维护深度。

?
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
program p2002;
    type
        tree=record
            l,r,father,size:longint;
        end;
    var
        t:array[0..200100] of tree;
        root:array[0..200100] of boolean;
        z,i,j,n,m,k1,k2,k3:longint;
    procedure change(k:longint);
        begin
            t[t[k].l].father:=k; t[t[k].r].father:=k;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(i:longint);
        begin
            z:=t[i].r;t[i].r:=t[z].l;t[t[i].r].father:=i;t[z].l:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure zag(i:longint);
       begin
            z:=t[i].l;t[i].l:=t[z].r;t[t[i].l].father:=i;t[z].r:=i;
            if i=t[t[i].father].l then t[t[i].father].l:=z else
            if i=t[t[i].father].r then t[t[i].father].r:=z;
            t[z].father:=t[i].father;t[i].father:=z;
            root[z]:=root[i] xor root[z];
            root[i]:=root[i] xor root[z];
            t[i].size:=t[t[i].l].size+t[t[i].r].size+1;
            t[z].size:=t[t[z].l].size+t[t[z].r].size+1;
       end;
    procedure up(k1:longint);
        var
            i,j:longint;
        begin
          while root[k1]=false do
                if t[t[k1].father].l=k1 then zag(t[k1].father) else zig(t[k1].father);
        end;
    procedure all_change(k:longint);
        var
            f:longint;
        begin
            up(k);
            while t[k].father<>0 do begin
                f:=t[k].father;
                up(f);
                root[t[f].r]:=true; root[k]:=false;
                t[f].r:=k; t[f].size:=t[t[f].r].size+t[t[f].l].size+1;
                up(k);
            end;
        end;
    begin
        fillchar(root,sizeof(root),true);
        readln(n);
        fillchar(t,sizeof(t),0);
        for i:=1 to n do begin
            read(t[i].father); t[i].size:=1; t[i].father:=t[i].father+i; if t[i].father>n then t[i].father:=n+1;
        end;
        t[n+1].size:=1;
        readln(m);
        for i:=1 to m do begin
            read(k1,k2); inc(k2);
            if k1=1 then begin
                all_change(k2); writeln(t[t[k2].l].size);
            end else begin
                read(k3);
                up(k2); t[t[k2].l].father:=t[k2].father;
                root[t[k2].l]:=true; t[k2].l:=0;
                t[k2].father:=k2+k3; if t[k2].father>n then t[k2].father:=n+1;
                t[k2].size:=t[t[k2].r].size+1;
            end;
        end;

【BZOJ2049】【Sdoi2008】Cave 洞穴勘测

LCT，只需要维护联通。

?
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
program p2049;
    type
        tree=record
            l,r,father:longint;
        end;
    var
        t:array[0..500000] of tree;
        rev:array[0..500000] of boolean;
        i,j,n,k1,k2,k3,k4,m:longint;
        ch:char;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
        end;
    procedure zag(k:longint);
        var
            f:longint;
            bo:boolean;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k);
                t[k].r:=now;
                now:=k;
                k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k);
            fz(f); splay(k);
        end;
    procedure link(k1,k2:longint); 
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0;
        end;
    function findleft(k:longint):longint;
        begin
            pushdown(k);
            if t[k].l=0 then exit(k) else exit(findleft(t[k].l));
        end;
    begin
        readln(n,m);
        fillchar(rev,sizeof(rev),false);
        fillchar(t,sizeof(t),0);
        for i:=1 to m do begin
            read(ch);
            {for j:=1 to n do if rev[j]=true then writeln(true);}
            if ch='C' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                link(k1,k2);
            end else if ch='D' then begin
                for j:=1 to 6 do read(ch); readln(k1,k2);
                cut(k1,k2);
            end else begin
                for j:=1 to 4 do read(ch); readln(k1,k2);
                k3:=findleft(access(k1)); k4:=findleft(access(k2));
                if k3=k4 then writeln('Yes') else writeln('No');
            end;
        end;
    end.

【BZOJ2243】【SDOI2011】染色

LCT，需要一个区间覆盖的标记。

 

?
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
program p2243;
    type
        tree=record
            l,r,left,right,w,ans,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        rev:array[0..110000] of boolean;
        color:array[0..110000] of longint;
        n,m,i,j,k1,k2,k3:longint;
        ch:char;
    procedure changecolor(k1,k2:longint);
        begin
            if k1=0 then exit;
            color[k1]:=k2; t[k1].w:=k2; t[k1].left:=k2; t[k1].right:=k2; t[k1].ans:=1;
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure swap(var k1,k2:longint);
        var
            k:longint;
        begin
            k:=k1; k1:=k2; k2:=k;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            swap(t[k].l,t[k].r); swap(t[k].left,t[k].right); rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if color[k]<>-1 then begin
                changecolor(t[k].l,color[k]); changecolor(t[k].r,color[k]); color[k]:=-1;
            end;
        end;
    procedure change(k:longint);
        begin
            pushdown(t[k].l); pushdown(t[k].r);
            t[k].left:=t[t[k].l].left; t[k].right:=t[t[k].r].right;
            if t[k].left=-1 then t[k].left:=t[k].w;
            if t[k].right=-1 then t[k].right:=t[k].w;
            t[k].ans:=t[t[k].l].ans+t[t[k].r].ans+1;
            if t[k].w=t[t[k].l].right then dec(t[k].ans);
            if t[k].w=t[t[k].r].left then dec(t[k].ans);
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f); {change(k);}
        end;
    procedure splay(k:longint);
        begin
            pushdown(k);
            while splay_root(k)=true do
                if k=t[t[k].father].l then zig(k) else zag(k);
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        var
            f:longint;
        begin
            f:=access(k); fz(f); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); t[k1].father:=k2; f:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            f:longint;
        begin
            makeroot(k1); access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    function findanswer(k1,k2:longint):longint;
        var
            f:longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    procedure rebuild(k1,k2,k3:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); changecolor(k,k3);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(rev,sizeof(rev),false);
        fillchar(color,sizeof(color),-1);
        for i:=1 to n do begin
            read(t[i].w); t[i].left:=t[i].w; t[i].right:=t[i].w;
        end; readln;
        t[0].w:=-1; t[0].left:=-1; t[0].right:=-1;
        for i:=1 to n-1 do begin
            readln(k1,k2); link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='Q' then begin
                readln(k1,k2); writeln(findanswer(k1,k2));
            end else begin
                readln(k1,k2,k3); rebuild(k1,k2,k3);
            end;
        end;
    end.

【BZOJ2631】tree(伍一鸣)

双标记的LCT，PASCAL由于常熟原因T了一点。

?
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
program p2631;
    const
        modd=51061;
    type
        tree=record
            father,l,r,size:longint;
            w,ans:int64;
        end;
    var
        t:array[0..210000] of tree;
        x,y:array[0..210000] of int64;
        rev:array[0..210000] of boolean;
        i,j,n,m,k1,k2,k3:longint;
        ch:char;
    procedure chen(k1,k2:longint);
        begin
            if k1=0 then exit;
            x[k1]:=x[k1]*k2 mod modd; y[k1]:=y[k1]*k2 mod modd;
            t[k1].w:=t[k1].w*k2 mod modd; t[k1].ans:=t[k1].ans*k2 mod modd;
        end;
    procedure jia(k1,k2:longint);
        begin
            if k1=0 then exit;
         {   if y[k1]<>1 then begin
                chen(t[k1].l,y[k1]); chen(t[k1].r,y[k1]); y[k1]:=1;
            end;}
            x[k1]:=x[k1]+k2; t[k1].w:=t[k1].w+k2;  t[k1].ans:=t[k1].ans+k2*t[k1].size;
        end;
    procedure fz(k:longint);
        begin
            if k=0 then exit;
            t[k].l:=t[k].l xor t[k].r;
            t[k].r:=t[k].r xor t[k].l;
            t[k].l:=t[k].l xor t[k].r;
            rev[k]:=rev[k] xor true;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if rev[k]=true then begin
                fz(t[k].l); fz(t[k].r); rev[k]:=false;
            end;
            if y[k]<>1 then begin
                chen(t[k].l,y[k]); chen(t[k].r,y[k]); y[k]:=1;
            end;
            if x[k]<>0 then begin
                jia(t[k].l,x[k]); jia(t[k].r,x[k]); x[k]:=0;
            end;
        end;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[k].ans:=(t[t[k].l].ans+t[t[k].r].ans+t[k].w) mod modd;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
        end;
    procedure zig(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].l:=t[k].r; t[t[f].l].father:=f; t[k].r:=f; t[f].father:=k;
            change(f);
        end;
    procedure zag(k:longint);
        var
            f:longint;
        begin
            f:=t[k].father; pushdown(f); pushdown(k);
            if t[t[f].father].l=f then t[t[f].father].l:=k else if t[t[f].father].r=f then t[t[f].father].r:=k;
            t[k].father:=t[f].father; t[f].r:=t[k].l; t[t[f].r].father:=f; t[k].l:=f; t[f].father:=k;
            change(f);
        end;
    function splay_root(k:longint):boolean;
        begin
            exit((t[k].father<>0) and ((t[t[k].father].l=k) or (t[t[k].father].r=k)));
        end;
    procedure splay(k:longint);
        var
            f1,f2:longint;
        begin
            pushdown(k);
            while (splay_root(k)=true) do begin
                f1:=t[k].father; f2:=t[f1].father;
                if splay_root(f1)=false then begin
                    if k=t[t[k].father].l then zig(k) else zag(k);
                    break;
                end;
                pushdown(f2);
                if k=t[f1].l then begin
                    if f1=t[f2].l then begin zig(f1); zig(k); end else begin zig(k); zag(k); end;
                end else if f1=t[f2].l then begin zag(k); zig(k); end else begin zag(f1); zag(k); end;
            end;
            change(k);
        end;
    function access(k:longint):longint;
        var
            now:longint;
        begin
            now:=0;
            while k<>0 do begin
                splay(k); t[k].r:=now; change(k); now:=k; k:=t[k].father;
            end;
            exit(now);
        end;
    procedure makeroot(k:longint);
        begin
            fz(access(k)); splay(k);
        end;
    procedure link(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); t[k1].father:=k2; k:=access(k1);
        end;
    procedure cut(k1,k2:longint);
        var
            k:longint;
        begin
            makeroot(k1); k:=access(k2); splay(k2); t[t[k2].l].father:=0; t[k2].l:=0; change(k2);
        end;
    procedure add1(k1,k2,k3:longint);
        begin
            makeroot(k1); jia(access(k2),k3);
        end;
    procedure add2(k1,k2,k3:longint);
        begin
            makeroot(k1); chen(access(k2),k3);
        end;
    function findanswer(k1,k2:longint):longint;
        begin
            makeroot(k1); exit(t[access(k2)].ans);
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0);
        fillchar(x,sizeof(x),0);
        fillchar(rev,sizeof(rev),false);
        for i:=1 to n do begin
            y[i]:=1; t[i].size:=1; t[i].w:=1; t[i].ans:=1;
        end;
        for i:=1 to n-1 do begin
            readln(k1,k2);
            link(k1,k2);
        end;
        for i:=1 to m do begin
            read(ch);
            if ch='+' then begin
                readln(k1,k2,k3);
                add1(k1,k2,k3);
            end else if ch='/' then begin
                readln(k1,k2);
                writeln(findanswer(k1,k2));
            end else if ch='-' then begin
                read(k1,k2); cut(k1,k2);
                readln(k1,k2); link(k1,k2);
            end else begin
                readln(k1,k2,k3);
                add2(k1,k2,k3);
            end;
        end;
    end.
?
1
 
Category: 数据结构 | Tags: | Read Count: 1602
Small_feed 评论 (0)

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com