[NOI2005]维修数列 （推荐 Splay tree）
转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove
据说是NOI中巨恶心的一道数据结构题。
其中的插入，删除，反转在其它博文里都能找到。
这里有个求和，应该也比较容易，记录一下子树的和，然后记得更新就行了。
还有个更新操作，是把区间统一置数，也可以用延迟标记。
麻烦的是最大子列和。要记录左端的最大子列和，右端的最大子列和，以及整个区间的最大和。
在更新的时候，区间最大和，可能是左子树的最大和，右子树的最大和，左子树的右端+节点+右子树的左端，情况要分清楚
和一道经典的线段树差不多。毕竟Splay重要的是其它操作上的优势。
能AC这道题，太爽了。
#include<iostream>#include<cstring>#include<queue>#include<cstdio>#include<algorithm>#define N 500005#define inf 1<<29#define MOD 100000007#define LL long long#define Key_value ch[ch[root][1]][0]#define _match(a,b) ((a)==(b))using namespace std;int n,q,a[N];int size[N],pre[N],rev[N],sum[N],val[N],same[N];int ch[N][2],tot1,root,s[N],tot2,lx[N],rx[N],mx[N];//debug部分copy from hh void Treaval(int x) { if(x) { Treaval(ch[x][0]); printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d sum = %2d maxsum=%2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x],sum[x],mx[x]); Treaval(ch[x][1]); } } void debug() {printf("%d\n",root);Treaval(root);} //以上Debug void Update_Same(int r,int v){ if(!r) return; same[r]=1; val[r]=v; sum[r]=size[r]*v; lx[r]=rx[r]=mx[r]=max(v,v*size[r]);}void Update_Rev(int r){if(!r) return;swap(ch[r][0],ch[r][1]); swap(lx[r],rx[r]); //翻转时左右区间也交换！！！！rev[r]^=1;}void NewNode(int &r,int k,int father){ if(tot2) r=s[tot2--]; else r=++tot1; ch[r][0]=ch[r][1]=0; pre[r]=father; rev[r]=same[r]=0; val[r]=sum[r]=lx[r]=rx[r]=mx[r]=k;}void Push_Up(int x){ int l=ch[x][0],r=ch[x][1]; size[x]=size[l]+size[r]+1; sum[x]=sum[l]+sum[r]+val[x]; lx[x]=max(lx[l],sum[l]+val[x]+max(0,lx[r])); rx[x]=max(rx[r],sum[r]+val[x]+max(0,rx[l])); mx[x]=max(0,rx[l])+val[x]+max(0,lx[r]); mx[x]=max(mx[l],max(mx[r],mx[x]));}void Push_Down(int r){ if(rev[r]){ Update_Rev(ch[r][0]);Update_Rev(ch[r][1]); rev[r]=0; } if(same[r]){ Update_Same(ch[r][0],val[r]); Update_Same(ch[r][1],val[r]); same[r]=0; }}void Bulid(int &r,int L,int R,int father){ if(L>R) return ; int mid=(L+R)/2; NewNode(r,a[mid],father); Bulid(ch[r][0],L,mid-1,r); Bulid(ch[r][1],mid+1,R,r); Push_Up(r);}void Init(){ tot1=tot2=root=0; ch[root][0]=ch[root][1]=pre[root]=rev[root]=size[root]=same[root]=0;mx[root]=lx[root]=rx[root]=-inf;//因为这个地方找了半天 NewNode(root,-1,0); NewNode(ch[root][1],-1,root); Push_Up(root); Bulid(Key_value,1,n,ch[root][1]); Push_Up(ch[root][1]); Push_Up(root);}void Rotate(int x,int kind){ int y=pre[x]; Push_Down(y); Push_Down(x); ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y]) ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; Push_Up(y); } void Splay(int r,int goal){ Push_Down(r); while(pre[r]!=goal){ if(pre[pre[r]]==goal) Rotate(r,ch[pre[r]][0]==r); else{ int y=pre[r]; int kind=(ch[pre[y]][0]==y); if(ch[y][kind]==r){ Rotate(r,!kind); Rotate(r,kind); } else{ Rotate(y,kind); Rotate(r,kind); } } } Push_Up(r); if(goal==0) root=r; } void RotateTo(int k,int goal) { int r=root; Push_Down(r); while(size[ch[r][0]]!=k){ if(k<size[ch[r][0]]){ r=ch[r][0]; } else { k-=(size[ch[r][0]]+1); r=ch[r][1]; } Push_Down(r); } Splay(r,goal); } int Get_Kth(int r,int k){ Push_Down(r); int t=size[ch[r][0]]+1; if(t==k) return r; if(t>k) return Get_Kth(ch[r][0],k); else return Get_Kth(ch[r][1],k-t);}int Get_Min(int r){ Push_Down(r); while(ch[r][0]){ r=ch[r][0]; Push_Down(r); } return r;}int Get_Max(int r){ Push_Down(r); while(ch[r][1]){ r=ch[r][1]; Push_Down(r); } return r;}void Reversal(int pos,int k){ int x=Get_Kth(root,pos); Splay(x,0); int y=Get_Kth(root,pos+k+1); Splay(y,root); Update_Rev(Key_value);}int cnt;void InOrder(int r){ if(r==0) return; Push_Down(r); InOrder(ch[r][0]); if(cnt>=1&&cnt<=size[root]-2) printf("%d ",val[r]); cnt++; InOrder(ch[r][1]);}void Insert(int pos,int k){ int x=Get_Kth(root,pos); Splay(x,0); // RotateTo(pos,0); int m=Get_Min(ch[root][1]); Splay(m,root); Bulid(Key_value,1,k,ch[root][1]); Push_Up(ch[root][1]); Push_Up(root);}void erase(int r){ if(!r) return; s[++tot2]=r; erase(ch[r][0]); erase(ch[r][1]);}void Delete(int pos,int k){// RotateTo(pos,0); int x=Get_Kth(root,pos); Splay(x,0); int y=Get_Kth(root,pos+k+1); Splay(y,root); erase(Key_value); pre[Key_value]=0; Key_value=0; Push_Up(ch[root][1]); Push_Up(root);}void Make_same(int pos,int k,int v){ int x=Get_Kth(root,pos); Splay(x,0); int y=Get_Kth(root,pos+k+1); Splay(y,root); Update_Same(Key_value,v); Push_Up(ch[root][1]); Push_Up(root);}int Get_Sum(int pos,int k){ int x=Get_Kth(root,pos); Splay(x,0); int y=Get_Kth(root,pos+k+1); Splay(y,root); return sum[Key_value];}int Get_MaxSum(int pos,int k){int x=Get_Kth(root,pos); Splay(x,0); int y=Get_Kth(root,pos+k+1); Splay(y,root); return mx[Key_value];}int main(){ while(scanf("%d%d",&n,&q)!=EOF){ for(int i=1;i<=n;i++) scanf("%d",&a[i]); Init(); char str[10]; int pos,k,v; while(q--){ scanf("%s",str); if(!strcmp(str,"INSERT")){ scanf("%d%d",&pos,&k); for(int i=1;i<=k;i++) scanf("%d",&a[i]); Insert(pos+1,k); } else if(!strcmp(str,"DELETE")){ scanf("%d%d",&pos,&k); Delete(pos,k); } else if(!strcmp(str,"MAKE-SAME")){ scanf("%d%d%d",&pos,&k,&v); Make_same(pos,k,v); } else if(!strcmp(str,"REVERSE")){ scanf("%d%d",&pos,&k); Reversal(pos,k); } else if(!strcmp(str,"GET-SUM")){ scanf("%d%d",&pos,&k);cc++; printf("%d\n",Get_Sum(pos,k)); } else printf("%d\n",Get_MaxSum(1,size[root]-2)); } } return 0;}