splay可以用于维护序列，比如noi的维修序列，比如这道

发现当时splay没写总结，也没题解

然后重新写splay竟然耗了一个晚上

结果是因为max【0】没有附最小值！！血一样的教训

最后祭出inline大法才过，我的splay真的慢到吐血

{
     $inline on}{
     $M 1000000000,0,maxlongint}const  //mm=maxlongint>>2;  maxn=60000; var  size,left,right,mark,fa,value,max:array[0..maxn]of longint;  rev:array[0..maxn]of boolean;  root,i,j,k,l,n,m,tot,x:longint; function new:longint;inline;begin  inc(tot);  exit(tot);end; function mmax(x,y:longint):longint;inline;begin  if x
      
       0 then begin    value[x]:=value[x]+mark[x];    max[x]:=max[x]+mark[x];    inc(mark[left[x]],mark[x]);    inc(mark[right[x]],mark[x]);    mark[x]:=0;  end;end;procedure update(x:longint);inline;begin  pushdown(x);  pushdown(left[x]);  pushdown(right[x]);  size[x]:=size[left[x]]+size[right[x]]+1;  max[x]:=mmax(value[x],mmax(max[left[x]],max[right[x]]));end; procedure lt(x:longint);inline;var  u,k:longint;  flag:boolean;begin  pushdown(x);  pushdown(right[x]);  k:=right[x];  u:=fa[x];  if left[u]=x then flag:=true else flag:=false;  right[x]:=left[k];  fa[right[x]]:=x;  left[k]:=x;  fa[x]:=k;  update(x);  update(k);  fa[k]:=u;  if flag then left[u]:=k else right[u]:=k;end; procedure rt(x:longint);inline;var  u,k:longint;  flag:boolean;begin  pushdown(x);  pushdown(left[x]);  k:=left[x];  u:=fa[x];  if left[u]=x then flag:=true else flag:=false;  left[x]:=right[k];  fa[left[x]]:=x;  right[k]:=x;  fa[x]:=k;  update(x);  update(k);  fa[k]:=u;  if flag then left[u]:=k else right[u]:=k;end; procedure splay(x,u:longint);inline;begin  while fa[x]<>u do begin    if fa[fa[x]]=u then begin      if left[fa[x]]=x then rt(fa[x])        else lt(fa[x]);      exit;    end;    if left[fa[x]]=x then begin      if left[fa[fa[x]]]=fa[x] then rt(fa[fa[x]]);      rt(fa[x]);    end    else begin      if right[fa[fa[x]]]=fa[x] then lt(fa[fa[x]]);      lt(fa[x]);    end;  end;end; function find(x,y:longint):longint;inline;begin  pushdown(x);  if size[left[x]]=y-1 then exit(x);  if y<=size[left[x]] then exit(find(left[x],y))    else exit(find(right[x],y-1-size[left[x]]));end;  function change(j,k:longint):longint;inline;var  now:longint;begin  now:=find(root,j);  splay(now,0);  root:=now;  now:=find(root,k+2);  splay(now,root);  exit(now);end; function build(l,r:longint):longint;inline;var  mid,x:longint;begin  mid:=(l+r)>>1;  x:=new;  value[x]:=0;  size[x]:=r-l+1;  rev[x]:=false;  mark[x]:=0;  left[x]:=0;  right[x]:=0;  if l=r then begin    if (l=0) or (l=n+1) then value[x]:=-maxlongint>>1;    max[x]:=value[x];    exit(x);  end;  if l
       
        0 do begin    dec(m);    read(j);    if j=1 then begin      readln(j,k,l);      x:=change(j,k);      inc(mark[left[x]],l);      update(x);      update(root);    end    else    if j=2 then begin      readln(j,k);      x:=change(j,k);      rev[left[x]]:=rev[left[x]] xor true;      update(x);      update(root);    end    else begin      readln(j,k);      x:=change(j,k);      writeln(max[left[x]]);    end;  end;end.
       
      

 

splay还可以当普通的平衡树做？就是把旋转改为旋转为根？再找到题写吧。