1
9
2014
0

平衡树专题

 

好久没来这儿了,忙了好久的数据库结构,现在来除个草吧。

【BZOJ3223】【TYVJ1729】文艺平衡树

只需要一个翻转标记。华丽的nlogn复杂度。

program p3223;
    type
        tree=record
            rev:boolean;
            l,r,w,size,father:longint;
        end;
    var
        t:array[0..110000] of tree;
        i,j,n,len,k1,k2,m,k3:longint;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            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 reversal(k:longint);
        var
            i:longint;
        begin
            if k=0 then exit;
            i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i;
            t[k].rev:=not t[k].rev;
        end;
    procedure pushdown(k:longint);
        begin
            if k=0 then exit;
            if t[k].rev then begin 
                reversal(t[k].l); reversal(t[k].r); t[k].rev:=false;
            end;
        end;
    procedure zig(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].l:=t[f].r; t[f].r:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure zag(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            i:=t[f]; t[f]:=t[k]; t[k]:=i;
            t[k].r:=t[f].l; t[f].l:=k; t[f].father:=t[k].father; t[k].father:=f;
            change(k); change(f);
        end;
    procedure build(now,l,r:longint);
        var
            mid:longint;
        begin
            t[now].rev:=false; 
            mid:=(l+r) shr 1;  t[now].w:=mid;
            if mid>l then begin
                t[now].l:=len+1; inc(len); build(len,l,mid-1);
            end;
            if mid<r then begin
                t[now].r:=len+1; inc(len); build(len,mid+1,r);
            end;
            change(now);
        end;
    function find(now,k:longint):longint;
        var
            l,r:longint;
        begin
            pushdown(now);
            l:=t[now].l; r:=t[now].r;
            if t[l].size=k-1 then exit(now);
            if t[l].size<k-1 then exit(find(r,k-t[l].size-1));
            exit(find(l,k));
        end;
    procedure up(k1,k2:longint);
        var
            i,j:longint;
        begin
            if k1=k2 then exit;
            if t[k1].father=k2 then begin
                if t[k2].l=k1 then zig(k1) else zag(k1);
                exit;
            end;
            i:=t[k1].father; j:=t[i].father;
            if k1=t[i].l then begin
                if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(i); end;
            end else
                if i=t[j].l then begin zag(k1); zig(i); end else begin zag(i); zag(k1); end;
            up(j,k2);
        end;
    begin
        readln(n,m);
        len:=1;
        t[0].size:=0;
        build(1,0,n+1);
        for i:=1 to m do begin
            readln(k1,k2);
            k3:=find(1,k1);
            up(k3,1);
            t[0].size:=0;
            k3:=find(1,k2+2);
            up(k3,t[1].r);
            t[0].size:=0;
            reversal(t[t[1].r].l);
        end;
        for i:=1 to n do begin
            k3:=find(1,i+1);
            write(t[k3].w);
            if i<>n then write(' ');
        end; 
    end.

【BZOJ1058】【ZJOI2007】报表统计

一棵线段树一棵平衡树。可惜由于PASCAL的特性我T了那么一点点。

program p1058;
    const
        s1='IN_SORT_GAP';
    type
        splay=record
            l,r,father,ans,maxnum,minnum,w:longint;
        end;
        tree=record
            l,r,ans:longint;
        end;
    var
        t:array[0..2500000] of tree;
        x:array[0..1500000] of splay;
        y:array[0..500000] of longint;
        i,j,n,m,len,k1,k2,k3:longint;
        s:string;
        ch:char;
    function max(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    function min(k1,k2:longint):longint;
        begin
            if k1<k2 then exit(k1) else exit(k2);
        end;
    procedure change(k:longint);
        begin
            x[x[k].l].father:=k; x[x[k].r].father:=k; x[k].maxnum:=x[k].w; x[k].minnum:=x[k].w; x[k].ans:=maxlongint;
            if x[k].l<>0 then begin x[k].maxnum:=max(x[k].maxnum,x[x[k].l].maxnum); 
                x[k].minnum:=min(x[k].minnum,x[x[k].l].minnum); x[k].ans:=min(x[k].ans,x[x[k].l].ans);
                x[k].ans:=min(x[k].ans,x[k].w-x[x[k].l].maxnum);
            end;
            if x[k].r<>0 then begin x[k].maxnum:=max(x[k].maxnum,x[x[k].r].maxnum); 
                x[k].minnum:=min(x[k].minnum,x[x[k].r].minnum); x[k].ans:=min(x[k].ans,x[x[k].r].ans);
                x[k].ans:=min(x[k].ans,x[x[k].r].minnum-x[k].w);
            end;
        end;
    procedure zig(k:longint);
        var
            i:splay;
            f:longint;
        begin
            f:=x[k].father; i:=x[f]; x[f]:=x[k]; x[k]:=i;
            x[f].father:=x[k].father; x[k].l:=x[f].r; x[f].r:=k;
            x[k].father:=f; x[x[f].l].father:=f;
            change(k); 
        end;
    procedure zag(k:longint);
        var
            i:splay;
            f:longint;
        begin
            f:=x[k].father; i:=x[f]; x[f]:=x[k]; x[k]:=i;
            x[f].father:=x[k].father; x[k].r:=x[f].l; x[f].l:=k;
            x[k].father:=f; x[x[f].r].father:=f;
            change(k); 
        end;
    procedure up(k:longint);
        var
            k1,k2:longint;
        begin
            if k<=1 then exit;
            if x[k].father=1 then begin
                if x[1].l=k then zig(k) else zag(k);
                exit;
            end;
            k1:=x[k].father; k2:=x[k1].father;
            if k=x[k1].l then begin
                if k1=x[k2].l then begin zig(k1); zig(k); end else begin zig(k); zag(k1); end;
            end else begin
                if k1=x[k2].l then begin zag(k); zig(k1); end else begin zag(k1); zag(k); end;
            end;
            up(k2);
        end;
    procedure insert(k1,k2:longint);    
        var
            i,j:longint;
        begin
            if x[k1].w<k2 then begin
                if x[k1].r=0 then x[k1].r:=len else insert(x[k1].r,k2);
            end else
                if x[k1].l=0 then x[k1].l:=len else insert(x[k1].l,k2);
            change(k1);
        end;
    procedure buildtree(k1,k2,k3:longint);  
        begin
            if k2=k3 then begin
                t[k1].l:=y[k2]; t[k1].r:=y[k2]; t[k1].ans:=maxlongint; exit;
            end;
            buildtree(k1*2,k2,(k2+k3) shr 1);
            buildtree(k1*2+1,(k2+k3) shr 1+1,k3);
            t[k1].l:=t[k1*2].l; t[k1].r:=t[k1*2+1].r; 
            t[k1].ans:=min(min(t[k1*2].ans,t[k1*2+1].ans),abs(t[k1*2].r-t[k1*2+1].l));
        end;
    procedure maintain(k:longint);
        begin
            t[k].l:=t[k*2].l; t[k].r:=t[k*2+1].r; 
            t[k].ans:=min(min(t[k*2].ans,t[k*2+1].ans),abs(t[k*2].r-t[k*2+1].l));
        end;
    procedure rebuild(k1,k2,k3,k4,k5:longint);
        begin
            if (k2>k4) or (k3<k4) then exit;
            if (k2=k3) and (k2=k4) then begin
                t[k1].ans:=min(t[k1].ans,abs(t[k1].r-k5)); t[k1].r:=k5; exit;
            end;
            rebuild(k1*2,k2,(k2+k3) shr 1,k4,k5);
            rebuild(k1*2+1,(k2+k3) shr 1+1,k3,k4,k5);
            maintain(k1);
        end;
    begin
        readln(n,m); len:=0;
        fillchar(x,sizeof(x),0);
        for i:=1 to n do begin
            read(y[i]);
            inc(len); x[len].ans:=maxlongint; x[len].maxnum:=y[i]; x[len].minnum:=y[i]; x[len].w:=y[i];
            if len<>1 then begin
                insert(1,y[i]); up(len); change(1);
            end;
            up(len);
        end;
        buildtree(1,1,n);
        readln;
        for i:=1 to m do begin
            read(ch);
            if ch='I' then begin
                for j:=1 to 5 do read(ch); readln(k1,k2);
                rebuild(1,1,n,k1,k2);
                inc(len); x[len].ans:=maxlongint; x[len].maxnum:=y[i]; x[len].minnum:=y[i]; x[len].w:=k2;
                insert(1,k2); 
                up(len); change(1);
            end else begin
                readln(s);
                if s=s1 then writeln(x[1].ans) else writeln(t[1].ans);
            end;
        end;
    end.

【BZOJ1251】序列终结者

一个区间加标记一个翻转标记。

 

program p1251;
    type
        tree=record
            w,add,fz,ans,f,father,l,r,size:int64;
        end;
    var
        t:array[0..200000] of tree;
        i,j,n,m,k1,k2,k3,k4,len,k5,k6,root:longint;
    function max(k1,k2:int64):int64;
        begin
            if k1<k2 then exit(k2) else exit(k1);
        end;
    procedure change(k:longint);
        begin
            if k=0 then exit;
            t[k].size:=t[t[k].l].size+t[t[k].r].size+1;
            t[k].ans:=max(t[k].w,max(t[t[k].l].ans,t[t[k].r].ans))+t[k].add;
        end;
    procedure fanzhuan(k:longint);
        var
            i,j:longint;
        begin
            i:=t[k].l; t[k].l:=t[k].r; t[k].r:=i; t[k].fz:=t[k].fz xor 1;
        end;
    procedure pushdown(k:longint);
        begin
            t[k].w:=t[k].w+t[k].add;
            if t[k].fz=1 then begin
                fanzhuan(t[k].l); fanzhuan(t[k].r);
            end;
            inc(t[t[k].l].add,t[k].add);  inc(t[t[k].l].ans,t[k].add);
            inc(t[t[k].r].add,t[k].add);  inc(t[t[k].r].ans,t[k].add);
            t[k].fz:=0; t[k].add:=0;
        end;
    procedure zig(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            if t[f].father<>0 then begin
                if t[t[f].father].l=f then t[t[f].father].l:=k else t[t[f].father].r:=k;
            end;
            t[k].father:=t[f].father; t[f].father:=k; t[f].l:=t[k].r; t[k].r:=f; t[t[f].l].father:=f;
            change(f); 
        end;
    procedure zag(k:longint);
        var
            i:tree;
            f:longint;
        begin
            f:=t[k].father;
            pushdown(f); pushdown(k);
            if t[f].father<>0 then begin
                if t[t[f].father].l=f then t[t[f].father].l:=k else t[t[f].father].r:=k;
            end;
            t[k].father:=t[f].father; t[f].father:=k; t[f].r:=t[k].l; t[k].l:=f; t[t[f].r].father:=f;
            change(f); 
        end;
    procedure insert(k1,k2:longint);
        begin
            if t[k1].f<k2 then begin
                if t[k1].r=0 then begin t[k1].r:=len; t[len].father:=k1; end else insert(t[k1].r,k2);
            end else if t[k1].l=0 then begin t[k1].l:=len; t[len].father:=k1; end else insert(t[k1].l,k2);
            change(k1);
        end;
    procedure up(k1,k2:longint);
        var
            i,j:longint;
        begin
            if (k1=k2) then exit;
            if t[k1].father=k2 then begin
                if t[k2].l=k1 then zig(k1) else zag(k1); change(k1);
                exit;
            end;
            i:=t[k1].father; j:=t[i].father;
            if k1=t[i].l then begin
                if i=t[j].l then begin zig(i); zig(k1); end else begin zig(k1); zag(k1); end;
            end else
                if i=t[j].l then begin zag(k1); zig(k1); end else begin zag(i); zag(k1); end;
            if j=k2 then exit;
            up(k1,k2);
        end;
    function findwhere(k1,k2:longint):longint;
        begin
            pushdown(k1);
            if t[t[k1].l].size=k2-1 then exit(k1);
            if t[t[k1].l].size<k2-1 then exit(findwhere(t[k1].r,k2-t[t[k1].l].size-1));
            exit(findwhere(t[k1].l,k2));
        end;
    begin
        readln(n,m);
        fillchar(t,sizeof(t),0); len:=0; t[0].ans:=-maxlongint*1000; root:=1;
        for i:=0 to n+1 do begin
            inc(len); t[len].w:=0; t[len].size:=1; t[len].f:=i; t[len].ans:=i;
            if len<>1 then begin
                insert(root,i); up(len,root); root:=len;
            end;
        end;
        for i:=1 to m do begin
            read(k1,k2,k3);
            k5:=findwhere(root,k2); up(k5,root);root:=k5; k5:=findwhere(root,k3+2); up(k5,t[root].r);
            if k1=1 then begin
                read(k4); inc(t[t[t[root].r].l].add,k4); change(t[t[root].r].l); change(t[root].r); change(root);
            end else if k1=2 then fanzhuan(t[t[root].r].l)
            else writeln(t[t[t[root].r].l].ans);
        end;
    end.
Category: 数据结构 | Tags: | Read Count: 913

登录 *


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