[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;
}