剧恶心的splay……
为什么在bzoj上是超时，在自己的电脑上测的是栈溢出……
const maxn=;
maxc=;
var
n,m,i,j,y,root,x,posi,t,head:longint;
ch:char;
op:array[..maxn] of boolean;
l,r,a,next,c,mc,s,ma,mb,sum:array[..maxn] of longint;
function max(x,y:longint):longint;
begin
if x>y then exit(x) else exit(y);
end;
procedure update(x:longint);
var ls,rs:longint;
begin
ls:=l[x];rs:=r[x];
sum[x]:=sum[ls]+sum[rs]+a[x];
ma[x]:=max(ma[ls],sum[ls]+ma[rs]+a[x]);
mb[x]:=max(mb[rs],sum[rs]+mb[ls]+a[x]);
mc[x]:=max(mc[ls],mc[rs]);
mc[x]:=max(mc[x],mb[ls]+ma[rs]+a[x]);
s[x]:=s[ls]+s[rs]+;
end;
procedure r_rotate(var x:longint);
var y:longint;
begin
y:=l[x];l[x]:=r[y];r[y]:=x;update(x);x:=y;
end;
procedure l_rotate(var x:longint);
var y:longint;
begin
y:=r[x];r[x]:=l[y];l[y]:=x;update(x);x:=y;
end;
procedure put(x,y:longint;flag:boolean);
var tmp:longint;
begin
if x= then exit;
if flag then
begin
tmp:=l[x];l[x]:=r[x];r[x]:=tmp;
tmp:=ma[x];ma[x]:=mb[x];mb[x]:=tmp;
op[x]:=not op[x];
end;
if y< then
begin
c[x]:=y;a[x]:=y;sum[x]:=s[x]*y;
mc[x]:=max(,sum[x]);
ma[x]:=mc[x];mb[x]:=mc[x];
if mc[x]= then mc[x]:=y;
end;
end;
procedure splay(var x:longint;y:longint);
var tmp:longint;
begin
put(l[x],c[x],op[x]);put(r[x],c[x],op[x]);
op[x]:=false;c[x]:=maxc;tmp:=s[l[x]]+;
if y=tmp then exit;
if y>tmp then
begin
splay(r[x],y-tmp);l_rotate(x);
end
else
begin
splay(l[x],y);r_rotate(x);
end;
end;
procedure build(var x:longint;lx,rx:longint);
begin
if lx>rx then exit;
x:=(lx+rx)>>;
build(l[x],lx,x-);
build(r[x],x+,rx);
update(x);
end;
procedure release(x:longint);
begin
if x= then exit;
next[x]:=head;head:=x;
release(l[x]);release(r[x]);
end;
procedure init;
begin
readln(n,m);root:=;
fillchar(c,sizeof(c),);
a[]:=-;a[n+]:=-;mc[]:=-;
for i:= to n+ do read(a[i]);readln;
head:=n+;
for i:=head+ to maxn do next[i-]:=i;
build(root,,n+);
end;
procedure main;
begin
for m:= to m do
begin
read(ch);
case ch of
'I':begin
while ch<>' ' do read(ch);
read(posi,t);
splay(root,posi+);
for t:= to t do
begin
read(y);x:=head;head:=next[head];
a[x]:=y;l[x]:=l[root];l[root]:=x;
r[x]:=;c[x]:=maxc;op[x]:=false;
update(x);
end;
update(root);
end;
'D':begin
while ch<>' ' do read(ch);
read(posi,t);
splay(root,posi);
splay(root,posi+t+);
release(r[l[root]]);r[l[root]]:=;
update(l[root]);update(root);
end;
'M':begin
read(ch);read(ch);
case ch of
'K':begin
while ch<>' ' do read(ch);
read(posi,t,x);
splay(root,posi);
splay(root,posi+t+);
put(r[l[root]],x,false);
update(l[root]);update(root);
end;
'X':writeln(mc[root]);
end;
end;
'R':begin
while ch<>' ' do read(ch);
read(posi,t);
splay(root,posi);
splay(root,posi+t+);
put(r[l[root]],maxc,true);
update(l[root]);update(root);
end;
'G':begin
while ch<>' ' do read(ch);
read(posi,t);
splay(root,posi);
splay(root,posi+t+);
update(root);
writeln(sum[r[l[root]]]);
end;
end;
readln;
end;
end;
begin
init;
main;
end.
声亦香的题解：http://blog.sina.com.cn/s/blog_86942b1401016dhb.html
可是他的两个程序交上去也是一样的结果……