Description
Input
输入的第1 行包含两个数N 和M(M ≤20 000)，N 表示初始时数列中数的个数，M表示要进行的操作数目。
第2行包含N个数字，描述初始时的数列。
以下M行，每行一条命令，格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数，数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个，输入文件大小不超过20MBytes。
Output
对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。
Sample Input
9 8
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
2 -6 3 5 1 -5 -3 6 3
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
Sample Output
-1
10
1
10
10
1
10
题解：
平衡树的模板题，要用上翻转标记、统一赋值标记，维护区间和、区间最大左子串、区间最大右子串、区间最大子串。
代码：
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[..]of longint;
c:array[..,..]of longint;
q:array[..]of longint;
ch:array[..]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,]; r:=c[x,];
sum[x]:=sum[l]+sum[r]+v[x];
size[x]:=size[l]+size[r]+;
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,]; r:=c[x,];
if tag[x]> then
begin
tag[x]:=; rev[x]:=;
if l> then begin tag[l]:=; v[l]:=v[x]; sum[l]:=v[x]*size[l]; end;
if r> then begin tag[r]:=; v[r]:=v[x]; sum[r]:=v[x]*size[r]; end;
if v[x]>= then
begin
if l> then begin mx[l]:=sum[l]; rx[l]:=sum[l]; lx[l]:=sum[l]; end;
if r> then begin mx[r]:=sum[r]; rx[r]:=sum[r]; lx[r]:=sum[r]; end;
end else
begin
if l> then begin lx[l]:=; rx[l]:=; mx[l]:=v[x]; end;
if r> then begin lx[r]:=; rx[r]:=; mx[r]:=v[x]; end;
end;
end;
if rev[x]> then
begin
rev[x]:=rev[x] xor ; rev[l]:=rev[l] xor ; rev[r]:=rev[r] xor ;
ttt:=lx[l]; lx[l]:=rx[l]; rx[l]:=ttt; ttt:=lx[r]; lx[r]:=rx[r]; rx[r]:=ttt;
ttt:=c[l,]; c[l,]:=c[l,]; c[l,]:=ttt; ttt:=c[r,]; c[r,]:=c[r,]; c[r,]:=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,]=x then l:= else l:=; r:=l xor ;
if y=k then k:=x
ELSE BEGIN if c[z,]=y then c[z,]:=x else c[z,]:=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,]=x)xor(c[z,]=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,]; r:=c[x,];
if size[l]+=rk then exit(x);
if size[l]>=rk then exit(find(l,rk));
exit(find(r,rk-size[l]-));
end;
procedure rec(x:longint);
var l,r:longint;
begin
if x= then exit;
l:=c[x,]; r:=c[x,];
rec(l); rec(r); inc(qr); if qr= then qr:=; q[qr]:=x;
fa[x]:=; c[x,]:=; c[x,]:=;
tag[x]:=; rev[x]:=;
end;
function split(k,tot:longint):longint;
var x,y:longint;
begin
x:=find(rt,k); y:=find(rt,k+tot+);
splay(x,rt); splay(y,c[x,]);
exit(c[y,]);
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]:=; sum[x]:=size[x]*vall;
if vall>= then begin lx[x]:=sum[x]; rx[x]:=sum[x]; mx[x]:=sum[x]; end
else begin lx[x]:=; rx[x]:=; 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]= then
begin
rev[x]:=rev[x]xor ;
ttt:=c[x,]; c[x,]:=c[x,]; c[x,]:=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,]:=;
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 ; now:=id[mid]; last:=id[f];
if l=r then
begin
sum[now]:=a[l]; size[now]:=;
tag[now]:=; rev[now]:=;
if a[l]>= then begin lx[now]:=a[l]; rx[now]:=a[l]; mx[now]:=a[l]; end
else begin lx[now]:=; rx[now]:=; mx[now]:=a[l]; end;
end else begin build(l,mid-,mid); build(mid+,r,mid); end;
v[now]:=a[mid]; fa[now]:=last; update(now);
if mid>=f then c[last,]:=now else c[last,]:=now;
end;
procedure insert(k,tot:longint);
var i,z,x,y:longint;
begin
for i:= to tot do read(a[i]);
for i:= to tot do
if(ql<>qr)then begin inc(ql); if ql= then ql:=; id[i]:=q[ql]; end
else begin inc(cnt); id[i]:=cnt; end;
build(,tot,); z:=id[(+tot)div ];
x:=find(rt,k+); y:=find(rt,k+);
splay(x,rt); splay(y,c[x,]);
fa[z]:=y; c[y,]:=z;
update(y); update(x);
end;
begin
readln(n,m); mx[]:=-; a[]:=-; a[n+]:=-;
for i:= to n do read(a[i+]); readln;
for i:= to n+ do id[i]:=i;
build(,n+,);
rt:=(n+)div ; cnt:=n+;
for i:= to m do
begin
read(ch[],ch[],ch[]);
read(ch[]); while(not eoln)and(ch[]<>' ')do read(ch[]);
if(ch[]<>'M')or(ch[]<>'X')then begin read(k,tot); end;
if ch[]='I' then insert(k,tot);
if ch[]='D' then erase(k,tot);
if ch[]='M' then
begin
if ch[]='X' then writeln(mx[rt])
else begin read(vall); modify(k,tot,vall); end;
end;
if ch[]='R' then rever(k,tot);
if ch[]='G' then query(k,tot);
readln;
end;
end.
PASCAL(Splay)
#include<bits/stdc++.h>
using namespace std;
int tr[][],fa[],a[],root,cnt,n,m,j,k,l,ql,qr,q[];
char s[];
int newt(int v)
{
int x; if(ql!=qr){ ql++; if(ql>)ql=; x=q[ql]; }else x=++cnt;
tr[x][]=tr[x][]=tr[x][]=; tr[x][]=-;
tr[x][]=; tr[x][]=tr[x][]=tr[x][]=v; tr[x][]=tr[x][]=max(,v);
return x;
}
void up(int x)
{
int l=tr[x][],r=tr[x][];
tr[x][]=tr[l][]+tr[r][]+; tr[x][]=tr[l][]+tr[r][]+tr[x][];
tr[x][]=max(max(tr[l][],tr[r][]),tr[l][]+tr[x][]+tr[r][]);
tr[x][]=max(tr[l][],tr[l][]+tr[x][]+tr[r][]); tr[x][]=max(tr[r][],tr[l][]+tr[x][]+tr[r][]);
}
void down(int x)
{
if(x==)return;
int l=tr[x][],r=tr[x][]; if(l==)l=; if(r==)r=;
int x1=tr[x][],x2=tr[x][]; tr[x][]=-; tr[x][]=;
if(x1>-)
{
tr[l][]=tr[r][]=tr[l][]=tr[r][]=x1; tr[l][]=tr[l][]*x1; tr[r][]=tr[r][]*x1;
if(x1>=)
{
tr[l][]=tr[l][]=tr[l][]=tr[l][];
tr[r][]=tr[r][]=tr[r][]=tr[r][];
}else tr[l][]=tr[r][]=x1,tr[l][]=tr[l][]=tr[r][]=tr[r][]=;
}else
if(x2==)
{
tr[l][]^=; tr[r][]^=;
swap(tr[l][],tr[l][]); swap(tr[r][],tr[r][]);
swap(tr[l][],tr[l][]); swap(tr[r][],tr[r][]);
}
}
void del(int x)
{
if(x==)return;
qr++; if(qr>)qr=; q[qr]=x;
del(tr[x][]); del(tr[x][]);
}
int build(int l,int r)
{
int mid=(l+r)/; int x=newt(a[mid]);
if(l<mid)tr[x][]=build(l,mid-);
fa[tr[x][]]=x;
if(mid<r)tr[x][]=build(mid+,r);
fa[tr[x][]]=x;
up(x); return x;
}
pair<int,int> fl(int x,int y)
{
if(x==)return make_pair(,);
down(x);
if(tr[tr[x][]][]>=y)
{
pair<int,int> a=fl(tr[x][],y);
fa[a.second]=x; tr[x][]=a.second; up(x); a.second=x; return a;
}else
{
pair<int,int> a=fl(tr[x][],y-tr[tr[x][]][]-);
fa[a.first]=x; tr[x][]=a.first; up(x); a.first=x; return a;
}
}
int hb(int x,int y)
{
if(x==)return y; if(y==)return x;
down(x); down(y);
if(1ll*rand()*(tr[x][]+tr[y][])<1ll*RAND_MAX*tr[x][]){ int a=hb(tr[x][],y); fa[a]=x; tr[x][]=a; up(x); return x; }
int a=hb(x,tr[y][]); fa[a]=y; tr[y][]=a; up(y); return y;
}
int find(int x,int y)
{
down(x);
if(tr[tr[x][]][]>=y)return find(tr[x][],y);
if(tr[tr[x][]][]+==y)return x;
return find(tr[x][],y-tr[tr[x][]][]-);
}
int main()
{
srand();
scanf("%d%d",&n,&m); tr[][]=-/;
for(int i=;i<=n;i++)scanf("%d",&a[i]);
root=build(,n);
for(int i=;i<=m;i++)
{
scanf("%s",s+);
if(s[]=='I')
{
scanf("%d%d",&k,&n);
for(int j=;j<=n;j++)scanf("%d",&a[j]); int x=build(,n);
pair<int,int> a=fl(root,k); root=hb(hb(a.first,x),a.second);
}else
if(s[]=='D')
{
scanf("%d%d",&j,&k);
pair<int,int> a=fl(root,j-); pair<int,int> b=fl(a.second,k);
root=hb(a.first,b.second); del(b.first);
}else
if((s[]=='M')and(s[]=='K'))
{
scanf("%d%d%d",&j,&k,&l);
pair<int,int> a=fl(root,j-); pair<int,int> b=fl(a.second,k);
int x=b.first; tr[x][]=tr[x][]=l; tr[x][]=tr[x][]*l;
if(l>=)tr[x][]=tr[x][]=tr[x][]=tr[x][];else tr[x][]=l,tr[x][]=tr[x][]=;
root=hb(hb(a.first,x),b.second);
}else
if(s[]=='R')
{
scanf("%d%d",&j,&k);
pair<int,int> a=fl(root,j-); pair<int,int> b=fl(a.second,k);
int x=b.first; tr[x][]^=; swap(tr[x][],tr[x][]); swap(tr[x][],tr[x][]);
root=hb(hb(a.first,x),b.second);
}else
if(s[]=='G')
{
scanf("%d%d",&j,&k);
pair<int,int> a=fl(root,j-); pair<int,int> b=fl(a.second,k);
int x=b.first; printf("%d\n",tr[x][]); root=hb(hb(a.first,x),b.second);
}else printf("%d\n",tr[root][]);
}
}
C++(非旋转式Treap)