[关键字]：splay
[题目大意]：太麻烦了自己找题看吧。
//=============================================================================
[分析]：就是一些基本的splay操作。将一个区间[a,b]从splay树中取出来要先将a-1旋到根b+1旋到根的右子树，然后以根的右树的左树为根的子树就是区间[a,b]。每个splay树中的节点要保存：数值dat，子书大小size、sum区间和、maxsum最大子段和，mls从左开始连续的最大子段和，mrs同样；same是否要改为普通值，rev是否需翻转。同时为了免去NULL的判断，先新建一个新的null节点作为结束的标志，并提前在splay中加入两个节点一个在头一个在尾免去插入时对边界的的判断。首先说插入到a后面，其实就是插入到[a,a+1]中间，先将要插入的数列拍成一条链然后将a旋到根，a+1旋到根的右树，然后将这条链接到根的右树的左树。删除a以后的数字操作就是，旋转a到根，旋转b到根的右树，然后删掉根的右树的左树就行了。修改操作要记录个bool值判断是否要修改，如果需要修改就把bool值下传并维护sum数组为size*dat，如果改成了负值sum=修改的负值，maxsum、mls、mrs同理。翻转操作也需要一个bool，如果需要翻转就将左右子树和mls、mrs交换同时更改儿子bool值——取反。求和操作只要提取出[a,b]然后输出它所对应的sum值，求最大自序列和则要输出root的maxsum域。后两个操作知识提取值，但之前对于这两个操作需要的值得维护很重要。
[代码]：
View Code #include#include #include #include #include using namespace std; const int MAXN=2850003; const int MAXL=500001; const int INF=100000000; struct node { node *f,*c[2]; int size,dat,sum,maxsum,mls,mrs; bool same,rev; }SS[MAXN],*null,*root; int n,m,SC,pos,tot,c; int a[MAXL]; char s1[20]; node *New(int dat,node *f) { node *e=SS+ ++SC; e->size=1; e->f=f; e->dat=e->sum=e->maxsum=e->mls=e->mrs=dat; e->c[0]=e->c[1]=null; e->same=e->rev=0; return e; } void Update(node *v) { if (v==null) return; v->size=v->c[0]->size+v->c[1]->size+1; v->sum=v->c[0]->sum+v->c[1]->sum+v->dat; v->mls=v->c[0]->mls; v->mls=max(v->mls,v->c[0]->sum+v->dat); v->mls=max(v->mls,v->c[0]->sum+v->dat+v->c[1]->mls); v->mrs=v->c[1]->mrs; v->mrs=max(v->mrs,v->c[1]->sum+v->dat); v->mrs=max(v->mrs,v->c[1]->sum+v->dat+v->c[0]->mrs); v->maxsum=v->dat; v->maxsum=max(v->maxsum,v->c[0]->maxsum); v->maxsum=max(v->maxsum,v->c[1]->maxsum); v->maxsum=max(v->maxsum,v->c[0]->mrs+v->dat); v->maxsum=max(v->maxsum,v->c[1]->mls+v->dat); v->maxsum=max(v->maxsum,v->c[0]->mrs+v->dat+v->c[1]->mls); } void Push_down(node *v) { if (v==null) return; if (v->same) { v->same=0; v->c[0]->same=v->c[1]->same=1; v->c[0]->dat=v->c[1]->dat=v->dat; v->sum=v->maxsum=v->mls=v->mrs=v->dat*v->size; if (v->dat<0) v->maxsum=v->mls=v->mrs=v->dat; } if (v->rev) { v->rev=0; swap(v->c[0],v->c[1]); v->c[0]->rev^=1,v->c[1]->rev^=1; swap(v->mls,v->mrs); } } void Debug(node *v) { if (v==null) return; Push_down(v); Debug(v->c[0]); printf("%d ",v->dat); Debug(v->c[1]); } void Prepare() { SC=-1; null=NULL; null=New(-INF,NULL); null->size=0; root=New(-INF,null); root->c[1]=New(-INF,root); null->sum=root->sum=root->c[1]->sum=0; Update(root); } void Rotate(node *x,int o) { node *y=x->f; Push_down(x->c[0]),Push_down(x->c[1]),Push_down(y->c[!o]); y->c[o]=x->c[!o]; y->c[o]->f=y; x->f=y->f; if (y->f->c[0]==y) x->f->c[0]=x; else x->f->c[1]=x; y->f=x; x->c[!o]=y; Update(y); if (root==y) root=x; } void Splay(node *x,node *fa) { Push_down(x); while (x->f!=fa) { if (x->f->f==fa) { if (x->f->c[0]==x) Rotate(x,0); else Rotate(x,1); } else if (x->f->f->c[0]==x->f) { if (x->f->c[0]==x) Rotate(x->f,0),Rotate(x,0); else Rotate(x,1),Rotate(x,0); } else if (x->f->c[1]==x) Rotate(x->f,1),Rotate(x,1); else Rotate(x,0),Rotate(x,1); } Update(x); } void Select(int k,node *fa) { int temp; node *t; for (t=root;;) { Push_down(t); //printf("%d %d\n",k,t->c[0]->size); temp=t->c[0]->size; if (temp+1==k) break; if (k<=temp) t=t->c[0]; else k-=temp+1,t=t->c[1]; } Splay(t,fa); } void Insert(int pos,int tot,int *a) { node *t,*z; t=z=New(a[1],null); for (int i=2;i<=tot;++i) z=z->c[1]=New(a[i],z); //printf("%d %d %d\n",root->size,root->c[0]->size,root->c[1]->size); Select(pos+1,null); Select(pos+2,root); root->c[1]->c[0]=t; t->f=root->c[1]; Splay(z,null); } void Delete(int pos,int tot) { Select(pos,null); Select(pos+tot+1,root); root->c[1]->c[0]=null; Splay(root->c[1],null); } int GETSUM(int pos,int tot) { Select(pos,null); Select(pos+tot+1,root); //printf("%d\n",root->c[1]->c[0]->dat); //printf("%d %d %d\n",root->c[1]->c[0]->size,root->c[1]->c[0]->dat,root->c[1]->c[0]->sum); Push_down(root->c[1]->c[0]); //Debug(root); return root->c[1]->c[0]->sum; } void REVERSE(int pos,int tot) { Select(pos,null); Select(pos+tot+1,root); root->c[1]->c[0]->rev^=1; Splay(root->c[1]->c[0],null); } void MAKESUM(int pos,int tot,int c) { Select(pos,null); Select(pos+tot+1,root); root->c[1]->c[0]->same=1; //printf("%d\n",root->c[1]->c[0]->dat); root->c[1]->c[0]->dat=c; Splay(root->c[1]->c[0],null); } int MAXSUM() { Push_down(root); Update(root); return root->maxsum; } int main() { freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); scanf("%d%d",&n,&m); Prepare(); for (int i=1;i<=n;++i) scanf("%d",&a[i]); Insert(0,n,a); for (int i=1;i<=m;++i) { scanf("%s",s1); if (s1[0]=='I') { scanf("%d%d",&pos,&tot); for (int i=1;i<=tot;++i) scanf("%d",&a[i]); Insert(pos,tot,a); //Debug(root); //printf("\n"); } if (s1[0]=='D') { scanf("%d%d",&pos,&tot); Delete(pos,tot); //Debug(root); //printf("\n"); } if (s1[0]=='M' && s1[2]=='K') { scanf("%d%d%d",&pos,&tot,&c); MAKESUM(pos,tot,c); //Debug(root); //printf("\n"); } if (s1[0]=='R') { scanf("%d%d",&pos,&tot); REVERSE(pos,tot); //Debug(root); //printf("\n"); } if (s1[0]=='G') { scanf("%d%d",&pos,&tot); printf("%d\n",GETSUM(pos,tot)); } if (s1[0]=='M' && s1[2]=='X') printf("%d\n",MAXSUM()); } return 0; }