BZOJ 1500 维修序列 Splay

2019-11-08 01:45:49

字体：大中小

来源：转载

供稿：网友

题目链接： (http://www.lydsy.com/JudgeOnline/PRoblem.php?id=1500) 各种区间操作，但是方法都是统一的对于操作区间[L,R] 先把(L-1)旋转到根节点，再把(R+1)旋转到根的右儿子，那么需要操作的区间[L,R]就是根的右儿子的左儿子。但是L==1和R==n都需要特判，非常麻烦。所以不妨在前后都加一个数字，变成N+2长度的序列，就避免了特判。另外，对于插入操作，先把要插入的数列建成一棵新的平衡树，在接到原来的树上。插入量巨大，删除的时候要遍历一遍子树，回收垃圾。注意有负数的情况，更新Max的时候非常容易忽略。

代码：

#include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<vector> using namespace std; const int maxn=1000000+5;const int inf = 0x3f3f3f3f;int n,m,A[maxn];int Root,tot;int Q[maxn],rear;int fa[maxn],ch[maxn][2],sum[maxn],size[maxn],lm[maxn],rm[maxn],Max[maxn];int lazy[maxn],rev[maxn],val[maxn];char op[35];template <typename T> inline void _read(T &x){ char ch=getchar(); bool mark=false; for(;!isdigit(ch);ch=getchar())if(ch=='-')mark=true; for(x=0;isdigit(ch);ch=getchar())x=x*10+ch-'0'; if(mark)x=-x; } inline int Newnode(int key,int father){ int o; if(rear) o= Q[rear--]; else o= ++tot; fa[o]= father; size[o]=1; lm[o]=rm[o]=sum[o]=Max[o]=val[o]= key; lazy[o]=rev[o]=0; ch[o][0]=ch[o][1]=0; return o;}// splay基本操作 inline void Maintain(int o){ int ls= ch[o][0],rs=ch[o][1]; size[o]= size[ls]+size[rs]+1; sum[o]= sum[ls]+sum[rs]+val[o]; lm[o]= max(lm[ls],sum[ls]+val[o]+max(lm[rs],0)); rm[o]= max(rm[rs],sum[rs]+val[o]+max(rm[ls],0)); Max[o]= max(Max[ls],Max[rs]); Max[o]= max(Max[o],max(rm[ls],0)+val[o]+max(lm[rs],0));}int Build(int L,int R,int father){ if(L>R) return 0; int mid= (L+R)>>1; int o = Newnode(A[mid],father); ch[o][0]= Build(L,mid-1,o); ch[o][1]= Build(mid+1,R,o); Maintain(o); return o;}inline void Update_val(int o,int v){ if(!o) return; lazy[o]=1;val[o]=v ; sum[o]= size[o]*v; Max[o]= lm[o]= rm[o]= max(size[o]*v,v);}inline void Update_rev(int o){ if(!o) return ; rev[o]^=1; swap(ch[o][0],ch[o][1]); swap(lm[o],rm[o]);}inline void pushdown(int o){ int ls = ch[o][0],rs= ch[o][1]; if(lazy[o]){ Update_val(ls,val[o]); Update_val(rs,val[o]); lazy[o]=0; } if(rev[o]){ Update_rev(ls); Update_rev(rs); rev[o]=0; }}inline void Rotate(int x,int f){ int y=fa[x],z=fa[y]; ch[z][ch[z][1]==y]=x; fa[x]=z; fa[ch[x][f]]= y; ch[y][f^1]=ch[x][f]; ch[x][f]=y; fa[y]=x; Maintain(y); Maintain(x);}int q[maxn],tail;inline void splay(int x,int aim){ tail=0; q[++tail]=x; for(int i=x;i!=aim;i=fa[i]){ q[++tail]= fa[i];} while(tail) pushdown(q[tail--]); int o= fa[aim]; while(fa[x]!=o){ int y=fa[x],z=fa[y]; if(z!=o){ int f= (ch[z][1]==y); if(ch[y][f]==x) Rotate(y,f^1),Rotate(x,f^1); else Rotate(x,f),Rotate(x,f^1); } else Rotate(x,ch[y][0]==x); } Maintain(x); if(!o) Root= x;} int FindKth(int k){ int cur=Root; while(true){ pushdown(cur); if(size[ch[cur][0]]+1==k) return cur; else if(size[ch[cur][0]] >= k ) cur= ch[cur][0]; else k-= size[ch[cur][0]]+1,cur=ch[cur][1]; }}// Splay ends here.//Operationsint GetSum(int pos,int cnt){ splay(FindKth(pos),Root); splay(FindKth(pos+1+cnt),ch[Root][1]); return sum[ch[ch[Root][1]][0]];}void Recycle(int o){ Q[++rear]= o; if(ch[o][0]) Recycle(ch[o][0]); if(ch[o][1]) Recycle(ch[o][1]);}void Delete(int pos,int cnt){ splay(FindKth(pos),Root); splay(FindKth(pos+1+cnt),ch[Root][1]); int o= ch[Root][1]; fa[ch[o][0]]=0; Recycle(ch[o][0]); fa[ch[o][0]]=0; ch[o][0]=0; Maintain(o);Maintain(Root);}void Make_Same(int pos,int cnt,int v){ splay(FindKth(pos),Root); splay(FindKth(pos+1+cnt),ch[Root][1]); Update_val(ch[ch[Root][1] ] [0],v); Maintain(ch[Root][1]); Maintain(Root);}void Reverse(int pos,int cnt){ splay(FindKth(pos),Root); splay(FindKth(pos+1+cnt),ch[Root][1]); Update_rev(ch[ch[Root][1] ] [0] ); Maintain(ch[Root][1]); Maintain(Root);}void Insert(){ int pos,cnt,i; _read(pos); _read(cnt); for(i=1;i<=cnt;i++) _read(A[i]); splay(FindKth(pos+1),Root); splay(FindKth(pos+2),ch[Root][1]); ch[ch[Root][1]][0]= Build(1,cnt,ch[Root][1]); Maintain(ch[Root][1]); Maintain(Root);}void Max_Sum(int pos,int cnt){ splay(FindKth(pos),Root); splay(FindKth(pos+1+cnt),ch[Root][1]); printf("%d/n",Max[ch[ch[Root][1]][0]]);}void Init(){ int i; for(i=2;i<=n+1;i++) _read(A[i]); A[1]=A[n+2]= -1; Root= Build(1,n+2,0);}void put(){ int sz= size[Root]; cout<<"Array: "; for(int i=1;i<=sz;i++)cout<<val[FindKth(i)]<<" "; cout<<endl;}int main(){ //freopen("data.in","r",stdin); //freopen("myans.out","w",stdout); int i,j,x,y,c; _read(n); _read(m); for(i=0;i<maxn;i++)Max[i]= - inf ; Init(); while(m--){ scanf("%s",op+1); if(op[1]=='I') Insert(); else if(op[1]=='D'){ _read(x); _read(y); Delete(x,y); } else if(op[1]=='M' && op[3]=='K'){ _read(x); _read(y); _read(c); Make_Same(x,y,c); } else if(op[1]=='R'){ _read(x); _read(y); Reverse(x,y); } else if(op[1]=='G'&&op[5]=='S'){ _read(x); _read(y); printf("%d/n",GetSum(x,y)); } else if(op[1]=='M' && op[5]=='S')Max_Sum(1,size[Root]-2); //put(); } return 0;}

上一篇：hdu5256 序列变换 dp LIS

下一篇：Servlet学习笔记