陈年老题。。。
我就$%^&。。。
码了4k多。。。
主要就是用splay，然后处理区间上的东西
区间反转就和模板一样，但是要记得反转leftmax和rightmax
区间赋值就把那个区间提取出来，然后给子树根打个same标记，表示下面的全一样。
区间求最大子段和就和线段树的套路一样。
区间插入就先弄好一颗平衡树，然后把原平衡树的根右儿子的的左儿子空出来插这个。
求sum就多加一个sum就行了。删除就把它弄成一个单独的子树。
具体看代码吧。。。
#include <iostream> #include <queue> #include <cstdio> #include <cstring> using namespace std; queue<int>q; const int N=1000005; int val[N],fa[N],ch[N][2],siz[N],sum[N],lmx[N],rmx[N],mx[N],a[N],n,m,rt,id[N],tot; bool rev[N],sam[N]; char opt[20]; void pushup(int x) { sum[x]=sum[ch[x][1]]+sum[ch[x][0]]+val[x]; siz[x]=siz[ch[x][1]]+siz[ch[x][0]]+1; mx[x]=max(val[x]+lmx[ch[x][1]]+rmx[ch[x][0]],max(mx[ch[x][0]],mx[ch[x][1]])); lmx[x]=max(lmx[ch[x][0]],sum[ch[x][0]]+lmx[ch[x][1]]+val[x]); rmx[x]=max(rmx[ch[x][1]],sum[ch[x][1]]+rmx[ch[x][0]]+val[x]); return; } void pushdown(int x) { if(sam[x]) { rev[x]=sam[x]=0; if(ch[x][0]) sam[ch[x][0]]=1,val[ch[x][0]]=val[x],sum[ch[x][0]]=val[x]*siz[ch[x][0]]; if(ch[x][1]) sam[ch[x][1]]=1,val[ch[x][1]]=val[x],sum[ch[x][1]]=val[x]*siz[ch[x][1]]; if(val[x]>=0) { if(ch[x][0]) lmx[ch[x][0]]=rmx[ch[x][0]]=mx[ch[x][0]]=sum[ch[x][0]]; if(ch[x][1]) lmx[ch[x][1]]=rmx[ch[x][1]]=mx[ch[x][1]]=sum[ch[x][1]]; } else { if(ch[x][0]) lmx[ch[x][0]]=rmx[ch[x][0]]=0,mx[ch[x][0]]=val[x]; if(ch[x][1]) lmx[ch[x][1]]=rmx[ch[x][1]]=0,mx[ch[x][1]]=val[x]; } } if(rev[x]) { rev[x]=0; rev[ch[x][0]]^=1;rev[ch[x][1]]^=1; swap(lmx[ch[x][0]],rmx[ch[x][0]]);swap(lmx[ch[x][1]],rmx[ch[x][1]]); swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);swap(ch[ch[x][0]][0],ch[ch[x][0]][1]); } } void rotate(int x) { int f=fa[x],ff=fa[f]; bool tag=x==ch[fa[x]][1]; pushdown(f);pushdown(x); ch[f][tag]=ch[x][tag^1]; fa[ch[f][tag]]=f; fa[f]=x; fa[x]=ff; ch[x][tag^1]=f; if(ff) ch[ff][f==ch[ff][1]]=x; pushup(f);pushup(x); } void splay(int x,int tar) { for(int f;(f=fa[x])!=tar;rotate(x)) if(fa[f]!=tar)rotate((x==ch[fa[x]][1])==(f==ch[fa[f]][1])?f:x); if(!tar) rt=x; } int getpos(int x) { int now=rt; while(1) { pushdown(now); if(siz[ch[now][0]]>=x) now=ch[now][0]; else { x-=siz[ch[now][0]]+1; if(!x) return now; now=ch[now][1]; } } } void rec(int x) { if(ch[x][0]) rec(ch[x][0]); if(ch[x][1]) rec(ch[x][1]); q.push(x); fa[x]=ch[x][0]=ch[x][1]=val[x]=sam[x]=rev[x]=0; } void del(int sta,int len) { int x=getpos(sta),y=getpos(sta+len+1); splay(x,0),splay(y,x); rec(ch[y][0]); ch[y][0]=0; pushup(y); pushup(x); } void modify(int sta,int len,int v) { int x=getpos(sta),y=getpos(sta+len+1); splay(x,0),splay(y,x); x=ch[y][0];y=fa[x]; val[x]=v; sum[x]=siz[x]*v;sam[x]=1; if(v>=0) lmx[x]=rmx[x]=v=mx[x]=sum[x]; else lmx[x]=rmx[x]=0,mx[x]=v; pushup(y),pushup(fa[y]); } void reve(int sta,int len) { int x=getpos(sta),y=getpos(sta+len+1); splay(x,0),splay(y,x); x=ch[y][0],y=fa[x]; if(!sam[x]) { rev[x]^=1; swap(ch[x][0],ch[x][1]); swap(lmx[x],rmx[x]); pushup(y),pushup(fa[y]); } } void build(int f,int l,int r) { int mid=l+r>>1,now=id[mid],pre=id[f]; if(l==r) { mx[now]=sum[now]=a[l]; sam[now]=rev[now]=0; lmx[now]=rmx[now]=max(a[l],0); siz[now]=1; } if(l<mid) build(mid,l,mid-1); if(mid<r) build(mid,mid+1,r); val[now]=a[mid];fa[now]=pre; pushup(now);ch[pre][mid>=f]=now; } void insert(int sta,int len) { for(int i=1;i<=len;i++) scanf("%d",&a[i]); for(int i=1;i<=len;i++) {if(q.size()) id[i]=q.front(),q.pop();else id[i]=++tot;} build(0,1,len); int mid=id[(1+len)>>1],x=getpos(sta+1),y=getpos(sta+2); splay(x,0),splay(y,x); fa[mid]=y;ch[y][0]=mid; pushup(y),pushup(x); } void getsum(int sta,int len) { int x=getpos(sta),y=getpos(sta+len+1); splay(x,0),splay(y,x); x=ch[y][0],y=fa[x]; printf("%d ",sum[x]); } int main() { scanf("%d%d",&n,&m); mx[0]=a[1]=-0x3f3f3f3f,a[n+2]=-0x3f3f3f3f; for(int i=1;i<=n;i++) scanf("%d",&a[i+1]); for(int i=1;i<=n+2;i++) id[i]=i; build(0,1,n+2); rt=(n+3)>>1;tot=n+2; int len,sta,v; while(m--) { scanf("%s",opt); if(opt[0]=='I') { scanf("%d%d",&sta,&len); insert(sta,len); } if(opt[0]=='D') { scanf("%d%d",&sta,&len); del(sta,len); } if(opt[0]=='M') { if(opt[2]=='X'){printf("%d ",mx[rt]);} else {scanf("%d%d%d",&sta,&len,&v),modify(sta,len,v);} } if(opt[0]=='R') { scanf("%d%d",&sta,&len); reve(sta,len); } if(opt[0]=='G') scanf("%d%d",&sta,&len),getsum(sta,len); } }