bzoj1251: 序列终结者 (splay)

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

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

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

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

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

{$inline on}
{$M 1000000000,0,maxlongint}
const//mm=maxlongint>>2;maxn=60000;varsize,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;
begininc(tot);exit(tot);
end;function mmax(x,y:longint):longint;inline;
beginif x<y then exit(y);exit(x)
end;procedure swap(var x,y:longint);inline;
vari:longint;
begini:=x;x:=y;y:=i;
end;procedure pushdown(x:longint);inline;
beginif x=0 then exit;if rev[x] then beginswap(left[x],right[x]);rev[left[x]]:=rev[left[x]] xor true;rev[right[x]]:=rev[right[x]] xor true;rev[x]:=false;end;if mark[x]<>0 then beginvalue[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;
beginpushdown(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;
varu,k:longint;flag:boolean;
beginpushdown(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;
varu,k:longint;flag:boolean;
beginpushdown(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;
beginwhile fa[x]<>u do beginif fa[fa[x]]=u then beginif left[fa[x]]=x then rt(fa[x])else lt(fa[x]);exit;end;if left[fa[x]]=x then beginif left[fa[fa[x]]]=fa[x] then rt(fa[fa[x]]);rt(fa[x]);endelse beginif right[fa[fa[x]]]=fa[x] then lt(fa[fa[x]]);lt(fa[x]);end;end;
end;function find(x,y:longint):longint;inline;
beginpushdown(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;
varnow:longint;
beginnow:=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;
varmid,x:longint;
beginmid:=(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 beginif (l=0) or (l=n+1) then value[x]:=-maxlongint>>1;max[x]:=value[x];exit(x);end;if l<mid then beginleft[x]:=build(l,mid-1);fa[left[x]]:=x;end;if mid<r then beginright[x]:=build(mid+1,r);fa[right[x]]:=x;end;update(x);exit(x);
end;beginreadln(n,m);max[0]:=-maxlongint;root:=build(0,n+1);while m>0 do begindec(m);read(j);if j=1 then beginreadln(j,k,l);x:=change(j,k);inc(mark[left[x]],l);update(x);update(root);endelseif j=2 then beginreadln(j,k);x:=change(j,k);rev[left[x]]:=rev[left[x]] xor true;update(x);update(root);endelse beginreadln(j,k);x:=change(j,k);writeln(max[left[x]]);end;end;
end.

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