首页 > 代码库 > BZOJ1500 NOI2005 维修数列 平衡树
BZOJ1500 NOI2005 维修数列 平衡树
题意：给定一个数列，要求维护：1、在p之后加入tot个数 2、删除p之后tot个数 3、将p之后tot个数修改为c 4、翻转p之后tot个数 5、输出p之后tot个数的和 6、输出整个数列的最大子段和。
题解：平衡树很经典的题目了……主要说一下4和6操作，4的话因为翻转操作是可以分治的，所以可以用翻转标记；6我们维护一个节点所维护的区间的的最大子段和ms、从左开始的最大子段和lms、从右开始的最大子段和rms，显然有ms=max(lchild->ms,rchild->ms,lchild->rms(或0)+v+rchild->lms(或0))
Treap和Splay各敲了一遍，现在想想当初学复数个平衡树的我真是个傻X
Splay：
#include <cstdio>#include <climits>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=500000+2;typedef struct NODE{ NODE *child[2],*f; int s,c,v,ms,lms,rms; bool same,rev; NODE(){} NODE(int _v,NODE *_f):s(_v),v(_v),ms(_v),lms(_v),rms(_v),f(_f){}} *TREE;TREE root,Null;int N,M,a[MAXN];char Order[20+2];TREE NewNode(int v,TREE f){ TREE x=new NODE(v,f); x->child[0]=x->child[1]=Null; x->c=1,x->same=x->rev=0; return x;}void Initialization(){ Null=NewNode(SHRT_MIN,0),Null->c=0; root=NewNode(SHRT_MIN,Null); root->child[1]=NewNode(SHRT_MIN,root); Null->s=root->s=root->child[1]->s=0;}void Pushup(TREE x){ if(x==Null) return; x->c=x->child[0]->c+x->child[1]->c+1; x->s=x->child[0]->s+x->child[1]->s+x->v; x->ms=max(x->child[0]->ms,x->child[1]->ms); x->ms=max(x->ms,max(0,x->child[0]->rms)+x->v+max(0,x->child[1]->lms)); x->lms=max(x->child[0]->lms,x->child[0]->s+x->v+max(0,x->child[1]->lms)); x->rms=max(x->child[1]->rms,x->child[1]->s+x->v+max(0,x->child[0]->rms));}void Pushdown(TREE x){ if(x==Null) return; if(x->rev){ swap(x->child[0],x->child[1]),swap(x->lms,x->rms); x->child[0]->rev^=1,x->child[1]->rev^=1,x->rev=0; } if(x->same){ x->s=x->c*x->v,x->same=0; x->ms=x->lms=x->rms=max(x->v,x->s); x->child[0]->same=1,x->child[0]->v=x->v; x->child[1]->same=1,x->child[1]->v=x->v; }}void Rotate(TREE x,bool t){ TREE y=x->f; Pushdown(x->child[0]),Pushdown(x->child[1]),Pushdown(y->child[t]); y->child[!t]=x->child[t],x->child[t]->f=y,x->f=y->f; if(y->f->child[0]==y) y->f->child[0]=x; else y->f->child[1]=x; y->f=x,x->child[t]=y; Pushup(y),Pushup(x); if(y==root) root=x;}void Splay(TREE x,TREE y){ Pushdown(x); while(x->f!=y) if(x->f->f==y) if(x->f->child[0]==x) Rotate(x,1); else Rotate(x,0); else if(x->f->f->child[0]==x->f) if(x->f->child[0]==x) Rotate(x->f,1),Rotate(x,1); else Rotate(x,0),Rotate(x,1); else if(x->f->child[0]==x) Rotate(x,1),Rotate(x,0); else Rotate(x->f,0),Rotate(x,0);}void Select(int p,TREE y){ TREE x=root;Pushdown(x); while(p!=x->child[0]->c+1){ if(p<=x->child[0]->c) x=x->child[0]; else p-=x->child[0]->c+1,x=x->child[1]; Pushdown(x); } Splay(x,y);}void Insert(int p,int n,int *a){ TREE s,t; s=t=NewNode(a[1],Null); for(int i=2;i<=n;i++) t=t->child[1]=NewNode(a[i],t); Select(p+1,Null),Select(p+2,root); root->child[1]->child[0]=s,s->f=root->child[1]; Splay(t,Null);}void Erase(TREE x){ if(x==Null) return; Erase(x->child[0]),Erase(x->child[1]); delete x;}void Delete(int p,int n){ Select(p,Null),Select(p+n+1,root); Erase(root->child[1]->child[0]); root->child[1]->child[0]=Null; Splay(root->child[1],Null);}void Reverse(int p,int n){ Select(p,Null),Select(p+n+1,root); root->child[1]->child[0]->rev^=1; Splay(root->child[1]->child[0],Null);}int Summation(int p,int n){ Select(p,Null),Select(p+n+1,root); Pushdown(root->child[1]->child[0]); return root->child[1]->child[0]->s;}void Change(int p,int n,int v){ Select(p,Null),Select(p+n+1,root); root->child[1]->child[0]->same=1,root->child[1]->child[0]->v=v; Splay(root->child[1]->child[0],Null);}int Maximizing(){ Pushdown(root),Pushup(root); return root->ms;}int main(){ Initialization(); cin >> N >> M; for(int i=1;i<=N;i++) scanf("%d",a+i); Insert(0,N,a); for(int i=1,pos;i<=M;i++){ scanf("%s",Order); if(strstr(Order,"INSERT")){ scanf("%d %d",&pos,&N); for(int i=1;i<=N;i++) scanf("%d",a+i); Insert(pos,N,a); } if(strstr(Order,"DELETE")){ scanf("%d %d",&pos,&N); Delete(pos,N); } if(strstr(Order,"REVERSE")){ scanf("%d %d",&pos,&N); Reverse(pos,N); } if(strstr(Order,"GET-SUM")){ scanf("%d %d",&pos,&N); cout << Summation(pos,N) << endl; } if(strstr(Order,"MAKE-SAM")){ scanf("%d %d %d",&pos,&N,a); Change(pos,N,a[0]); } if(strstr(Order,"MAX-SUM")) cout << Maximizing() << endl; } return 0;}
Treap：
#include <ctime>#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm>using namespace std;const int MAXN=500000+2;typedef struct NODE{ NODE *child[2]; int c,v,s,key,ms,lms,rms; bool same,rev; NODE(){} NODE(int _v):v(_v),s(_v),ms(_v),lms(_v),rms(_v){}} *TREE;typedef pair<TREE,TREE> ROOT;TREE Null,root;int N,M,a[MAXN];char Order[20+2];TREE NewNode(int v){ TREE x=new NODE(v); x->child[0]=x->child[1]=Null; x->same=x->rev=0,x->c=1,x->key=rand(); return x;}void Initialization(){ srand(time(Null)); root=Null=NewNode(SHRT_MIN); Null->s=Null->c=0;}void Update_Rev(TREE x){ if(x==Null) return; swap(x->child[0],x->child[1]),swap(x->lms,x->rms); x->rev^=1;}void Update_Same(TREE x,int v){ if(x==Null) return; x->v=v,x->same=1,x->s=x->c*v; x->ms=x->lms=x->rms=max(x->v,x->s);}void Pushup(TREE x){ if(x==Null) return; x->c=x->child[0]->c+x->child[1]->c+1; x->s=x->child[0]->s+x->child[1]->s+x->v; x->ms=max(x->child[0]->ms,x->child[1]->ms); x->ms=max(x->ms,max(0,x->child[0]->rms)+x->v+max(0,x->child[1]->lms)); x->lms=max(x->child[0]->lms,x->child[0]->s+x->v+max(0,x->child[1]->lms)); x->rms=max(x->child[1]->rms,x->child[1]->s+x->v+max(0,x->child[0]->rms));}void Pushdown(TREE x){ if(x==Null) return; if(x->rev){ Update_Rev(x->child[0]),Update_Rev(x->child[1]); x->rev=0; } if(x->same){ Update_Same(x->child[0],x->v),Update_Same(x->child[1],x->v); x->same=0; }}ROOT Split(TREE x,int p){ if(x==Null) return ROOT(Null,Null); Pushdown(x); ROOT y; if(x->child[0]->c>=p){ y=Split(x->child[0],p); x->child[0]=y.second,y.second=x; } else{ y=Split(x->child[1],p-x->child[0]->c-1); x->child[1]=y.first,y.first=x; } Pushup(x); return y;}TREE Merge(TREE x,TREE y){ if(x==Null) return y; if(y==Null) return x; if(x->key<y->key){ Pushdown(x); x->child[1]=Merge(x->child[1],y); Pushup(x); return x; } else{ Pushdown(y); y->child[0]=Merge(x,y->child[0]); Pushup(y); return y; }}void Insert(int p,int n,int *a){ TREE x=NewNode(a[1]); for(int i=2;i<=n;i++) x=Merge(x,NewNode(a[i])); ROOT y=Split(root,p); root=Merge(y.first,Merge(x,y.second));}void Erase(TREE x){ if(x==Null) return; Erase(x->child[0]),Erase(x->child[1]); delete x;}void Delete(int p,int n){ ROOT x=Split(root,p-1),y=Split(x.second,n); Erase(y.first); root=Merge(x.first,y.second);}void Change(int p,int n,int v){ ROOT x=Split(root,p-1),y=Split(x.second,n); Update_Same(y.first,v); root=Merge(x.first,Merge(y.first,y.second));}void Reverse(int p,int n){ ROOT x=Split(root,p-1),y=Split(x.second,n); Update_Rev(y.first); root=Merge(x.first,Merge(y.first,y.second));}int Summation(int p,int n){ ROOT x=Split(root,p-1),y=Split(x.second,n); int ret=y.first->s; root=Merge(x.first,Merge(y.first,y.second)); return ret;}int Maximizing(){ return root->ms;}int main(){ Initialization(); cin >> N >> M; for(int i=1;i<=N;i++) cin >> a[i]; Insert(1,N,a); for(int i=1,pos;i<=M;i++){ scanf("%s",Order); if(strstr(Order,"INSERT")){ scanf("%d %d",&pos,&N); for(int i=1;i<=N;i++) scanf("%d",a+i); Insert(pos,N,a); } if(strstr(Order,"DELETE")){ scanf("%d %d",&pos,&N); Delete(pos,N); } if(strstr(Order,"REVERSE")){ scanf("%d %d",&pos,&N); Reverse(pos,N); } if(strstr(Order,"GET-SUM")){ scanf("%d %d",&pos,&N); cout << Summation(pos,N) << endl; } if(strstr(Order,"MAKE-SAM")){ scanf("%d %d %d",&pos,&N,a); Change(pos,N,a[0]); } if(strstr(Order,"MAX-SUM")) cout << Maximizing() << endl; } return 0;}
BZOJ1500 NOI2005 维修数列 平衡树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。