BZOJ 1500 [NOI2005 D1T2] 维修数列_综合

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

HINT

Source

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

splay~

splay无敌组合版……做完这一道都要升华了……

符号很多，要注意区分~

#include<cstdio>
#include<iostream>
#include<queue>
using namespace std;
#define inf 999999999int n,m,a[500001],x,y,z,root,fa[500001],sum[500001],c[500001][2],id[500001],siz[500001],mx[500001],cnt,lx[500001],rx[500001],tag[500001],v[500001];
bool rev[500001];
char s[10];
queue<int> q;int read()
{int totnum=0,f=1;char cc=getchar();while(cc<'0' || cc>'9') {if(cc=='-') f=-1;cc=getchar();}while(cc>='0' && cc<='9') {totnum=totnum*10+cc-'0';cc=getchar();}return totnum*f;
}void update(int u)
{int l=c[u][0],r=c[u][1];sum[u]=sum[l]+sum[r]+v[u];siz[u]=siz[l]+siz[r]+1;mx[u]=max(mx[l],mx[r]);mx[u]=max(mx[u],rx[l]+v[u]+lx[r]);lx[u]=max(lx[l],v[u]+sum[l]+lx[r]);rx[u]=max(rx[r],v[u]+sum[r]+rx[l]);
}void pushdown(int u)
{int l=c[u][0],r=c[u][1];if(tag[u]){rev[u]=tag[u]=0;if(l) tag[l]=1,v[l]=v[u],sum[l]=v[u]*siz[l];if(r) tag[r]=1,v[r]=v[u],sum[r]=v[u]*siz[r];if(v[u]>=0){if(l) lx[l]=rx[l]=mx[l]=sum[l];if(r) lx[r]=rx[r]=mx[r]=sum[r];}else{if(l) lx[l]=rx[l]=0,mx[l]=v[u];if(r) lx[r]=rx[r]=0,mx[r]=v[u];}}if(rev[u]){rev[u]=0;rev[l]^=1;rev[r]^=1;swap(c[l][0],c[l][1]);swap(c[r][0],c[r][1]);swap(lx[l],rx[l]);swap(lx[r],rx[r]);}
}void build(int l,int r,int k)
{if(l>r) return;int la=id[k],mid=(l+r)>>1,now=id[mid];if(l==r){tag[now]=rev[now]=0;mx[now]=sum[now]=a[l];siz[now]=1;if(a[l]>=0) lx[now]=rx[now]=a[l];else lx[now]=rx[now]=0;}else build(l,mid-1,mid),build(mid+1,r,mid);v[now]=a[mid];fa[now]=la;update(now);c[la][mid>=k]=now;
}void rotate(int x,int &k)
{int y=fa[x],z=fa[y],l,r;if(c[y][0]==x) l=0;else l=1;r=l^1;if(y==k) k=x;else if(c[z][0]==y) c[z][0]=x;else c[z][1]=x;fa[x]=z;fa[y]=x;fa[c[x][r]]=y;c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);
}void splay(int x,int &k)
{while(x!=k){int y=fa[x],z=fa[y];if(y!=k){if(c[z][0]==y ^ c[y][0]==x) rotate(x,k);else rotate(y,k);}rotate(x,k);}
}int findd(int u,int k)
{int l=c[u][0],r=c[u][1];if(rev[u] || tag[u]) pushdown(u);if(siz[l]+1==k) return u;if(siz[l]>=k) return findd(l,k);return findd(r,k-siz[l]-1);
}int kk(int l,int r)
{int x=findd(root,l),y=findd(root,l+r+1);splay(x,root);splay(y,c[x][1]);return c[y][0];
}void add(int u,int tot)
{for(int i=1;i<=tot;i++) a[i]=read();for(int i=1;i<=tot;i++)if(!q.empty()) id[i]=q.front(),q.pop();else id[i]=++cnt;build(1,tot,0);int x=findd(root,u+1),y=findd(root,u+2),z=id[(1+tot)>>1];splay(x,root);splay(y,c[x][1]);fa[z]=y;c[y][0]=z;update(y);update(x);
}void rec(int u)
{if(!u) return;int l=c[u][0],r=c[u][1];rec(l);rec(r);q.push(u);fa[u]=c[u][0]=c[u][1]=rev[u]=tag[u]=0;
}void del(int u,int tot)
{int x=kk(u,tot),y=fa[x];rec(x);c[y][0]=0;update(y);update(fa[y]);
}void chan(int u,int tot,int val)
{int x=kk(u,tot),y=fa[x];v[x]=val;tag[x]=1;sum[x]=v[x]*siz[x];if(val>=0) lx[x]=rx[x]=mx[x]=sum[x];else lx[x]=rx[x]=0,mx[x]=val;update(y);update(fa[y]);
}void rever(int u,int tot)
{int x=kk(u,tot),y=fa[x];if(!tag[x]){rev[x]^=1;swap(c[x][0],c[x][1]);swap(lx[x],rx[x]);update(y);update(fa[y]);}
}int main()
{n=read();m=read();a[1]=a[n+2]=mx[0]=-inf;for(int i=1;i<=n;i++) a[i+1]=read();for(int i=1;i<=n+2;i++) id[i]=i;cnt=n+2;build(1,n+2,0);root=(n+3)>>1;int pos,tot,val;while(m--){scanf("%s",s);switch(s[2]){case('S'):pos=read();tot=read();add(pos,tot);break;case('L'):pos=read();tot=read();del(pos,tot);break;case('K'):pos=read();tot=read();val=read();chan(pos,tot,val);break;case('V'):pos=read();tot=read();rever(pos,tot);break;case('T'):pos=read();tot=read();printf("%d\n",sum[kk(pos,tot)]);break;case('X'):printf("%d\n",mx[root]);break;}}return 0;
}