【jzoj2413】【NOI2005】【维护数列】【splay】

题目大意

　请写一个程序，要求维护一个数列，支持以下6种操作：（请注意，格式栏中的下划线‘ _ ’表示实际输入文件中的空格）

1. 插入 INSERT_posi_tot_c1_c2_…_ctot 在当前数列的第posi个数字后插入tot个数字：c1, c2, …, ctot；若在数列首插入，则posi为0

2. 删除 DELETE_posi_tot 从当前数列的第posi个数字开始连续删除tot个数字

3. 修改 MAKE-SAME_posi_tot_c 将当前数列的第posi个数字开始的连续tot个数字统一修改为c

4. 翻转 REVERSE_posi_tot 取出从当前数列的第posi个数字开始的tot个数字，翻转后放入原来的位置

5. 求和 GET-SUM_posi_tot 计算从当前数列开始的第posi个数字开始的tot个数字的和并输出

6. 求和最大的子列 MAX-SUM 求出当前数列中和最大的一段子列，并输出最大和

解题思路

建一棵splay，维护size，sum，左起最大子区间，右起最大子区间，最大子区间，区间赋值标记，区间翻转标记。

注意使用节点回收。

code

#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LF double #define LL long long #define Min(a,b) ((a<b)?a:b) #define Max(a,b) ((a>b)?a:b) #define Fo(i,j,k) for(int i=j;i<=k;i++) #define Fd(i,j,k) for(int i=j;i>=k;i--) using namespace std; int const Mxn=5*1e5,Inf=1e8; int N,M,Pon,A[Mxn+9],Val[Mxn+9],Size[Mxn+9],Sum[Mxn+9],Mx[Mxn+9], Lmx[Mxn+9],Rmx[Mxn+9],Fa[Mxn+9],Son[Mxn+9][2],Fill[Mxn+9],Swap[Mxn+9], Bin[Mxn+9],L,R,Tm; void Update(int Now){ L=Son[Now][0],R=Son[Now][1]; Size[Now]=Size[L]+Size[R]+1; Sum[Now]=Val[Now]+Sum[L]+Sum[R]; if(R){ Tm=Max(Mx[R],Val[Now]+Lmx[R]); Mx[Now]=Max(Val[Now],Tm); Lmx[Now]=Max(Val[Now],Val[Now]+Lmx[R]); Rmx[Now]=Max(Val[Now]+Sum[R],Rmx[R]); }else Mx[Now]=Lmx[Now]=Rmx[Now]=Val[Now]; if(L){ Tm=Max(Mx[L],Rmx[L]+Lmx[Now]); Mx[Now]=Max(Mx[Now],Tm); Lmx[Now]=Max(Lmx[L],Sum[L]+Lmx[Now]); Rmx[Now]=Max(Rmx[L]+Val[Now]+Sum[R],Rmx[Now]); } } int New(){ return (Bin[0])?Bin[Bin[0]--]:++Pon; } int Root,Pre,Now; int Make(){ Root=New(),Pre=Root,Now; Val[Root]=A[1];Fill[Root]=-Inf;Swap[Root]=0;Son[Root][0]=0; Tm=A[0]; Fo(i,2,Tm){ Now=New(); Val[Now]=A[i];Fill[Now]=-Inf;Swap[Now]=0; Son[Now][0]=0; Son[Pre][1]=Now; Fa[Now]=Pre; Pre=Now; } Son[Pre][1]=0; Size[Now=Pre]=1; while(Now!=Root){ Update(Now); Now=Fa[Now]; } Update(Now); return Root; } int Side(int Now){ Tm=Fa[Now]; return Son[Tm][1]==Now; } int F,T; void Rotate(int Now){ F=Fa[Now],T=Side(Now); Son[F][T]=Son[Now][!T]; Fa[Son[Now][!T]]=F;Tm=Side(F); Son[Fa[F]][Tm]=Now; Fa[Now]=Fa[F]; Son[Now][!T]=F; Fa[F]=Now; Update(F); Update(Now); } void Retag(int Now,int Tag){ if(!Now)return; int L=Son[Now][0],R=Son[Now][1]; if(Swap[Now]){ swap(Son[Now][0],Son[Now][1]); swap(Lmx[Now],Rmx[Now]); Swap[L]^=1; Swap[R]^=1; Swap[Now]=0; } if(Fill[Now]!=-Inf){ Val[Now]=Fill[Now]; Sum[Now]=Fill[Now]*Size[Now]; Mx[Now]=Lmx[Now]=Rmx[Now]=(Fill[Now]>0)?Sum[Now]:Fill[Now]; Fill[L]=Fill[R]=Fill[Now];Fill[Now]=-Inf; } if(Tag){ if(L)Retag(L,0); if(R)Retag(R,0); } } void Splay(int Now,int Pre){ while(Fa[Now]!=Pre){ Tm=Fa[Now];Retag(Tm,1); if(Fa[Tm]==Pre)Rotate(Now); else{ Retag(Fa[Tm],1); if(Side(Now)==Side(Tm))Rotate(Fa[Now]),Rotate(Now); else Rotate(Now),Rotate(Now); } } } int Kth(int Now,int Num){ while(1){ Retag(Now,1);Tm=Son[Now][0]; if(Size[Tm]>=Num)Now=Tm; else if(Size[Tm]+1==Num)return Now; else Num-=Size[Tm]+1,Now=Son[Now][1]; } } void Get(int Pos,int Tot,int &Tmp,int &Tmp2){ Splay(Tmp=Kth(Son[0][1],Pos),0); Splay(Tmp2=Kth(Son[Tmp][1],Tot),Tmp); } void Dele(int Now){ Bin[++Bin[0]]=Now; int L=Son[Now][0],R=Son[Now][1]; if(L)Dele(L); if(R)Dele(R); } int Get(){ char Ch=getchar();int V=0,T=1; while(((Ch<'0')||(Ch>'9'))&&(Ch!='-'))Ch=getchar(); if(Ch=='-')T=-1,Ch=getchar(); while((Ch>='0')&&(Ch<='9'))V=V*10+Ch-'0',Ch=getchar(); return V*T; } int main(){ freopen("d.in","r",stdin); freopen("d.out","w",stdout); N=Get();M=Get(); A[0]=N;Fo(i,1,N)A[i]=Get(); Son[0][1]=++Pon;Fa[Pon]=0;Size[1]=2; Son[1][1]=++Pon;Fa[Pon]=1;Size[2]=1; Fill[1]=Fill[2]=-Inf;Val[1]=Val[2]=-Inf/10; int Tmp=Make(); Son[2][0]=Tmp;Fa[Tmp]=2; Update(2); Update(1); char Ch;int Pos,Tot,Tmp2,C; Fo(cas,1,M){ Ch=getchar(); if((Ch<'A')||(Ch>'Z'))Ch=getchar(); if(Ch=='I'){ scanf("NSERT");Pos=Get();Tot=Get();Pos++; Get(Pos,1,Tmp,Tmp2); A[0]=Tot;Fo(i,1,Tot)A[i]=Get(); Tmp=Make(); Son[Tmp2][0]=Tmp;Fa[Tmp]=Tmp2; Update(Tmp2); Update(Son[0][1]); }else if(Ch=='D'){ scanf("ELETE");Pos=Get();Tot=Get();Pos++; Get(Pos-1,Tot+1,Tmp,Tmp2); Dele(Son[Tmp2][0]); Son[Tmp2][0]=0; Update(Tmp2); Update(Tmp); }else if(Ch=='M'){ Ch=getchar(); Ch=getchar(); if(Ch=='K'){ scanf("E-SAME");Pos=Get();Tot=Get();C=Get();Pos++; Get(Pos-1,Tot+1,Tmp,Tmp2); Fill[Son[Tmp2][0]]=C; Retag(Son[Tmp2][0],1); Update(Tmp2); Update(Tmp); }else{ scanf("-SUM\n"); printf("%d\n",Mx[Son[0][1]]); } }else if(Ch=='R'){ scanf("EVERSE");Pos=Get();Tot=Get();Pos++; Get(Pos-1,Tot+1,Tmp,Tmp2); Swap[Son[Tmp2][0]]=1; Retag(Son[Tmp2][0],1); Update(Tmp2); Update(Tmp); }else if(Ch=='G'){ scanf("ET-SUM");Pos=Get();Tot=Get();Pos++; Get(Pos-1,Tot+1,Tmp,Tmp2); Retag(Son[Tmp2][0],1); printf("%d\n",Sum[Son[Tmp2][0]]); } } return 0; }