裸的splay

今儿写的splay，由于自己刚开始学，发现几个容易漏掉的地方

1：开始给所有的儿子赋值为-1

2：给max[-1]赋值为-maxlongint

3：开始father[root]:=sroot

4：在find和rotate中的push_down

5：数组的下边界为-1

6：push_down中要给标签清空

7：build中要给tree数组赋值

8：rotate操作不熟悉

由于不熟悉，发现的问题有很多，以后多加练习就好了

/**************************************************************    Problem: 3223    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:4720 ms    Memory:2668 kb****************************************************************/ //By BLADEVILconst    sroot                           =-1;     var    n, m                            :longint;    x, y                            :longint;    a                               :array[-1..100010] of longint;    tree, size, father              :array[-1..100010] of longint;    son                             :array[-1..100010,0..1] of longint;    flag                            :array[-1..100010] of boolean;    root                            :longint;    i                               :longint;     procedure swap(var a,b:longint);var    c                               :longint;begin    c:=a; a:=b; b:=c;end;     procedure update(x:longint);begin    size[x]:=size[son[x,1]]+size[son[x,0]]+1;end;     procedure renew_reverse(x:longint);begin    swap(son[x,1],son[x,0]);    flag[x]:=not flag[x];end; procedure push_down(x:longint);var    l, r                            :longint;begin    l:=son[x,0]; r:=son[x,1];    if flag[x] then    begin        if l<>-1 then renew_reverse(l);        if r<>-1 then renew_reverse(r);        flag[x]:=false;    end;end;     function build(l,r:longint):longint;var    mid                             :longint;begin    mid:=(l+r) div 2;    build:=mid;    tree[mid]:=a[mid];    if mid-1>=l then    begin        son[mid,0]:=build(l,mid-1);        father[son[mid,0]]:=mid;    end;    if mid+1<=r then    begin        son[mid,1]:=build(mid+1,r);        father[son[mid,1]]:=mid;    end;    update(mid);end; function find(x:longint):longint;var    t                               :longint;begin    t:=root;    while true do    begin        push_down(t);        if size[son[t,0]]+1=x then exit(t);        if size[son[t,0]]+1>x then t:=son[t,0] else        begin            dec(x,size[son[t,0]]+1);            t:=son[t,1];        end;    end;end; procedure rotate(x,y:longint);var    f                               :longint;begin    push_down(x);    f:=father[x];    son[f,y]:=son[x,y xor 1];    father[son[x,y xor 1]]:=f;    if f=root then root:=x else        if f=son[father[f],0] then            son[father[f],0]:=x else            son[father[f],1]:=x;    father[x]:=father[f];    father[f]:=x;    son[x,y xor 1]:=f;    update(f);    update(x);end; procedure splay(x,y:longint);var    u, v                            :longint;begin    while father[x]<>y do    begin        if father[father[x]]=y then            rotate(x,ord(x=son[father[x],1])) else        begin            if x=son[father[x],0] then u:=1 else u:=-1;            if father[x]=son[father[father[x]],0] then v:=1 else v:=-1;            if u*v=1 then            begin                rotate(father[x],ord(x=son[father[x],1]));                rotate(x,ord(x=son[father[x],1]));            end else            begin                rotate(x,ord(x=son[father[x],1]));                rotate(x,ord(x=son[father[x],1]));            end;        end;    end;    update(x);end;     procedure reverse(l,r:longint);var    p                               :longint;begin    p:=find(l); splay(p,sroot);    p:=find(r+2); splay(p,root);    p:=son[son[root,1],0];    renew_reverse(p);end;     begin    fillchar(son,sizeof(son),255);    read(n,m);    for i:=1 to n do a[i]:=i;    inc(n);    root:=build(0,n);    father[root]:=sroot;    for i:=1 to m do    begin        read(x,y);        reverse(x,y);    end;    for i:=2 to n do write(find(i),' '); writeln;end.