虽然自己用普通线段树2s,ZKW线段树1s过了,为了学Splay还是写了Splay 4875ms过
(*        好像很多地方都可以优化,算了...        *)

蒟蒻代码->
( 由于不涉及Insert/Delete 所以查找节点直接用的值而不是size,这样会快一点 )
program poj3468;

type pnode=^tnode;
     tnode=record
        v,len,w:longint;
        sum,dlt:int64;
        p,l,r:pnode;
     end;

const maxn=100017;

var null,root,tp:pnode;
    n,cmd:longint;
    initial:array[0..maxn] of longint;

procedure splay_init;
begin
new(null);
with null^ do begin
        v:=0; len:=0; w:=0; dlt:=0; sum:=0;
        l:=null; r:=null; p:=null;
end;
root:=null;
end;

procedure pushupto(var i:pnode);
begin
i^.len:=i^.l^.len+i^.r^.len+1;
i^.sum:=i^.l^.sum+i^.l^.len*i^.l^.dlt
       +i^.r^.sum+i^.r^.len*i^.r^.dlt
       +i^.w;
end;

procedure pushdown(var i:pnode);
begin
if i^.dlt=0 then exit;
inc(i^.w,i^.dlt);
inc(i^.sum,i^.len*i^.dlt);
if i^.l<>null then inc(i^.l^.dlt,i^.dlt);
if i^.r<>null then inc(i^.r^.dlt,i^.dlt);
i^.dlt:=0;
end;

procedure build(var i:pnode;il,ir:longint);
var mid:longint;
begin
new(i); mid:=(il+ir)>>1;
i^.v:=mid;
i^.sum:=initial[mid]; i^.len:=ir-il+1;
i^.w:=initial[mid];   i^.dlt:=0;
if il<>ir then begin
        if il<=mid-1 then build(i^.l,il,mid-1) else i^.l:=null;
        if ir>=mid+1 then build(i^.r,mid+1,ir) else i^.r:=null;
        i^.l^.p:=i; i^.r^.p:=i;
        pushupto(i);
end else begin
        i^.l:=null; i^.r:=null;
end;
end;

procedure rrot(var i:pnode);
var lkid:pnode;
begin
pushdown(i); pushdown(i^.l);
lkid:=i^.l; i^.l:=lkid^.r; lkid^.r:=i;
lkid^.p:=i^.p; i^.p:=lkid; i^.l^.p:=i;
pushupto(i); pushupto(lkid);
if i=root then root:=lkid
else if lkid^.v<lkid^.p^.v then lkid^.p^.l:=lkid
else lkid^.p^.r:=lkid;
i:=lkid;
end;

procedure lrot(var i:pnode);
var rkid,tmp:pnode;
begin
pushdown(i); pushdown(i^.r);
rkid:=i^.r; i^.r:=rkid^.l; rkid^.l:=i;
rkid^.p:=i^.p; i^.p:=rkid; i^.r^.p:=i;
pushupto(i); pushupto(rkid);
if i=root then root:=rkid
else if rkid^.v<rkid^.p^.v then rkid^.p^.l:=rkid
else rkid^.p^.r:=rkid;
i:=rkid;
end;

procedure splay(var i,j:pnode);
var k:pnode;
begin
while i<>j do begin
        if i^.p=j then
                if i=j^.l then rrot(j)
                          else lrot(j)
        else if i=i^.p^.l then
                if i^.p=i^.p^.p^.l then begin
                        k:=i^.p^.p;     rrot(k);
                        k:=i^.p;        rrot(k);
                end else begin
                        k:=i^.p;        rrot(k);
                        k:=i^.p;        lrot(k);
                end
        else    if i^.p=i^.p^.p^.l then begin
                        k:=i^.p;        lrot(k);
                        k:=i^.p;        rrot(k);
                end else begin
                        k:=i^.p^.p;     lrot(k);
                        k:=i^.p;        lrot(k);

                end;
end;
end;

function getnode(i:longint):pnode;
begin
getnode:=root;
while (getnode<>null)and(getnode^.v<>i) do
        if i<getnode^.v then getnode:=getnode^.l else getnode:=getnode^.r;
end;

procedure init;
var i,j,k:longint;
begin
readln(n,cmd);
for i:=1 to n do read(initial[i]);
readln;
end;

procedure work;
var i,j,k:longint;
    op:char;
    tp:pnode;
begin
tp:=root;
while tp<>null do begin
        dec(tp^.len);
        tp:=tp^.l;
end;
tp:=root;
while tp<>null do begin
        dec(tp^.len);
        tp:=tp^.r;
end;
while cmd>0 do begin
        dec(cmd);
        read(op);
        case op of
                'Q':begin
                        readln(i,j);
                        tp:=getnode(i-1);       splay(tp,root);
                        tp:=getnode(j+1);       splay(tp,root^.r);
                        pushdown(root); pushdown(root^.r); pushdown(root^.r^.l);
                        writeln(root^.r^.l^.sum);
                end;
                'C':begin
                        readln(i,j,k);
                        tp:=getnode(i-1);       splay(tp,root);
                        tp:=getnode(j+1);       splay(tp,root^.r);
                        inc(root^.r^.l^.dlt,k);
                end;
        end;
end;
end;

begin
init;
splay_init;
build(root,0,n+1);
work;
end.

• Re:3468 Splay差点超时,不过还是可以过的 (19) ygw11223 2014-04-09 20:01:26
  • 现在发现我其实也写挫了 (21) Hoblovski 2014-04-13 19:46:40
• 无限ym fhq神牛的treap (310) Hoblovski 2014-06-20 12:10:25