LCT，传说中的动态树，写得我蛋疼啊。
【BZOJ2002】【hnoi2012】弹飞绵羊
裸LCT，只需要维护深度。
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，只需要维护联通。
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，需要一个区间覆盖的标记。
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了一点。
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.
评论 (0)
