BZOJ1500[NOI2005]维修数列

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

Sample Output

-1
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)