BZOJ1500[NOI2005]维修数列

var
  n,m,rt,cnt,i,j,k,tot,vall,ql,qr:longint;
  a,id,fa,sum,size,v,mx,lx,rx,tag,rev:array[0..1000005]of longint;
  c:array[0..1000005,0..2]of longint;
  q:array[0..1000005]of longint;
  ch:array[0..3]of char;
function max(a,b:longint):longint;
begin
  if a>b then exit(a);
  exit(b);
end;
procedure update(x:longint);
var l,r:longint;
begin
  l:=c[x,0]; r:=c[x,1];
  sum[x]:=sum[l]+sum[r]+v[x]; 
  size[x]:=size[l]+size[r]+1;
  mx[x]:=max(mx[l],mx[r]);
  mx[x]:=max(mx[x],rx[l]+v[x]+lx[r]); 
  lx[x]:=max(lx[l],sum[l]+v[x]+lx[r]);
  rx[x]:=max(rx[r],sum[r]+v[x]+rx[l]);
end;
procedure pushdown(x:longint);
var l,r,ttt:longint;
begin
  l:=c[x,0]; r:=c[x,1];
  if tag[x]>0 then
  begin
    tag[x]:=0; rev[x]:=0;
    if l>0 then begin tag[l]:=1; v[l]:=v[x]; sum[l]:=v[x]*size[l]; end;
    if r>0 then begin tag[r]:=1; v[r]:=v[x]; sum[r]:=v[x]*size[r]; end;
    if v[x]>=0 then
    begin
      if l>0 then begin mx[l]:=sum[l]; rx[l]:=sum[l]; lx[l]:=sum[l]; end;
      if r>0 then begin mx[r]:=sum[r]; rx[r]:=sum[r]; lx[r]:=sum[r]; end;
    end else
    begin
      if l>0 then begin lx[l]:=0; rx[l]:=0; mx[l]:=v[x]; end;
      if r>0 then begin lx[r]:=0; rx[r]:=0; mx[r]:=v[x]; end;
    end;
  end;
  if rev[x]>0 then
  begin
    rev[x]:=rev[x] xor 1; rev[l]:=rev[l] xor 1; rev[r]:=rev[r] xor 1;
    ttt:=lx[l]; lx[l]:=rx[l]; rx[l]:=ttt; ttt:=lx[r]; lx[r]:=rx[r]; rx[r]:=ttt;
    ttt:=c[l,0]; c[l,0]:=c[l,1]; c[l,1]:=ttt; ttt:=c[r,0]; c[r,0]:=c[r,1]; c[r,1]:=ttt;
  end;
end;  
procedure rotate(x:longint;var k:longint);
var y,z,l,r:longint;
begin
  y:=fa[x]; z:=fa[y];
  if c[y,1]=x then l:=1 else l:=0; r:=l xor 1;
  if y=k then k:=x
  ELSE BEGIN if c[z,1]=y then c[z,1]:=x else c[z,0]:=x; END;
  fa[c[x,r]]:=y; fa[y]:=x; fa[x]:=z;
  c[y,l]:=c[x,r]; c[x,r]:=y;
  update(y); update(x);
end;
procedure splay(x:longint; var k:longint);
var y,z:longint;
begin
  while x<>k do
  begin
    y:=fa[x]; z:=fa[y];
    if y<>k then
    begin
      if(c[y,0]=x)xor(c[z,0]=y)then rotate(x,k)
      else rotate(y,k);
    end;
    rotate(x,k);
  end;
end;
function find(x,rk:longint):longint;
var l,r:longint;
begin
  pushdown(x);
  l:=c[x,0]; r:=c[x,1];
  if size[l]+1=rk then exit(x);
  if size[l]>=rk then exit(find(l,rk));
  exit(find(r,rk-size[l]-1));
end;
procedure rec(x:longint);
var l,r:longint;
begin
  if x=0 then exit;
  l:=c[x,0]; r:=c[x,1];
  rec(l); rec(r); inc(qr); if qr=1000000 then qr:=1; q[qr]:=x;
  fa[x]:=0; c[x,0]:=0; c[x,1]:=0;
  tag[x]:=0; rev[x]:=0;
end;
function split(k,tot:longint):longint;
var x,y:longint;
begin
  x:=find(rt,k); y:=find(rt,k+tot+1);
  splay(x,rt); splay(y,c[x,1]);
  exit(c[y,0]);
end;
procedure query(k,tot:longint);
var x:longint;
begin
  x:=split(k,tot);
  writeln(sum[x]);
end;
procedure modify(k,tot,vall:longint);
var x,y,I:longint;
begin
  x:=split(k,tot);  y:=fa[x];
  v[x]:=vall; tag[x]:=1; sum[x]:=size[x]*vall; 
  if vall>=0 then begin lx[x]:=sum[x]; rx[x]:=sum[x]; mx[x]:=sum[x]; end
  else begin lx[x]:=0; rx[x]:=0; mx[x]:=vall; end;
  update(y); update(fa[y]);
end;
procedure rever(k,tot:longint);
var x,y,ttt:longint;
begin
  x:=split(k,tot); y:=fa[x];
  if tag[x]=0 then  
  begin
    rev[x]:=rev[x]xor 1;
    ttt:=c[x,0]; c[x,0]:=c[x,1]; c[x,1]:=ttt;
    ttt:=lx[x]; lx[x]:=rx[x]; rx[x]:=ttt;
    update(y); update(fa[y]);
  end;
end;
procedure erase(k,tot:longint);
var x,y:longint;
begin
  x:=split(k,tot); y:=fa[x];
  rec(x); c[y,0]:=0;
  update(y); update(fa[y]);
end;
procedure build(l,r,f:longint);
var mid,now,last:longint;
begin
  if l>r then exit;
  mid:=(l+r)div 2; now:=id[mid]; last:=id[f];
  if l=r then
  begin
    sum[now]:=a[l]; size[now]:=1;
    tag[now]:=0; rev[now]:=0;
    if a[l]>=0 then begin lx[now]:=a[l]; rx[now]:=a[l]; mx[now]:=a[l]; end
    else begin lx[now]:=0; rx[now]:=0; mx[now]:=a[l]; end;
  end else begin build(l,mid-1,mid); build(mid+1,r,mid); end;
  v[now]:=a[mid]; fa[now]:=last; update(now);
  if mid>=f then c[last,1]:=now else c[last,0]:=now;
end;
procedure insert(k,tot:longint);
var i,z,x,y:longint;
begin
  for i:=1 to tot do read(a[i]);
  for i:=1 to tot do
  if(ql<>qr)then begin inc(ql); if ql=1000000 then ql:=1; id[i]:=q[ql]; end
  else begin inc(cnt); id[i]:=cnt; end;
  build(1,tot,0); z:=id[(1+tot)div 2];
  x:=find(rt,k+1); y:=find(rt,k+2);
  splay(x,rt); splay(y,c[x,1]);
  fa[z]:=y; c[y,0]:=z;
  update(y); update(x);
end;
begin
  readln(n,m); mx[0]:=-100000000; a[1]:=-100000000; a[n+2]:=-100000000;
  for i:=1 to n do read(a[i+1]); readln;
  for i:=1 to n+2 do id[i]:=i;
  build(1,n+2,0);
  rt:=(n+3)div 2; cnt:=n+2;
  for i:=1 to m do
  begin
    read(ch[0],ch[1],ch[2]);
    read(ch[3]); while(not eoln)and(ch[3]<>‘ ‘)do read(ch[3]);
    if(ch[0]<>‘M‘)or(ch[2]<>‘X‘)then begin read(k,tot); end;
    if ch[0]=‘I‘ then insert(k,tot);
    if ch[0]=‘D‘ then erase(k,tot);
    if ch[0]=‘M‘ then
    begin
      if ch[2]=‘X‘ then writeln(mx[rt])
      else begin read(vall); modify(k,tot,vall); end;
    end;
    if ch[0]=‘R‘ then rever(k,tot);
    if ch[0]=‘G‘ then query(k,tot);
    readln;
  end;
end.