1
9
2014
0

LCT专题

 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.

Category: 数据结构 | Tags: | Read Count: 943

登录 *


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