Portal Gun:[BZOJ1500][NOI2005]维修数列
有一段时间没写博客了,最近在刚数据结构......各种板子背得简直要起飞,题目也是一大堆做不完,这里就挑一道平衡树的题来写写好了
关于这道题...该说什么好呢...网上好多人评论这道题又是难啊,又是要调很久什么的,还讲这是道平衡树的 boos 级别的题...看了题后,好像也没有说的这么难吧,思路比较简单,代码也不是特别长,splay也还算好码,虽然我这边现学 splay 现做确实花了不少时间,但总体来说这道题还是比较简单的.
题目中的很多操作( INSERT,DELETE,MAKE-SAME,REVERSE )都有一个共性,是要操作从 pos 开始,往后一段长度的区间,这儿就有这样一个小套路:
1.对于 INSERT ,我们把 pos 旋转到根, pos+1 旋转到根的右儿子,显然这时 pos+1 的左儿子为空,那么我们要插入就好办了,将要插入的序列建成一颗小树,直接将小树的根插入到 pos 的左儿子就完成了整个操作.
2. 同样,对于其他几个操作,我们需要调整的是 pos 到 pos+tot 这一段,像 INSERT 那样,将 pos 旋转到根, pos+tot 旋转到根的右儿子,这时要操作的就是 pos+tot 的左儿子,这应该很好理解吧.以上是这些操作的共性.
详细的,对于 DELETE ,我们从 pos+tot 的左儿子开始,向下递归删除,为了防止空间的浪费,可以开个栈来存放被删除节点以备后面的 INSERT 使用. MAKE-SMAE 和 REVERSE 也都是递归处理,给每个节点分别记 tag 和 rev ,tag 表示是否进行 MAKE-SAME 操作, rev 表示是否 REVERSE ,就像线段树里的 lazy ,如果你想问 REVERSE 怎么完成, swap 不就得了...
至于 GET-SUM 和 MAX-SUM ,线段树你会吧......子节点递归更新父亲就好了......
以下是代码( 函数有点多,建议从 main() 开始阅读,顺着各个操作去阅读这些函数会比较有条理 ):
先容我吐槽几句:这个 gi() 好丑......本来我的 gi() 只有两行的,但两行的 gi() 放上来会超边框非常不爽,只好扩成现在这个......对于这个 gi() ,想吐槽的发到评论全就好了......
这个 gi() 是不是优美多了, hhh
#include<iostream> #include<cstdio> #include<cstdlib> #define inf (1<<30) #define maxn (510010) #define ll long long #define il inline #define RG register using namespace std; il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar(); if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; } struct node{ bool rev,tag; int fa,son[2],w,size,sum,lmax,rmax,ans; }t[maxn];//lmax表示左端点在内的最大区间和,rmax相反,ans为整个区间的最大区间和 int n,Q,cnt,root,sta[maxn],top,a[maxn]; il int newnode(){ int num; if(top) num=sta[top--]; else num=++cnt; t[num].son[0]=t[num].son[1]=t[num].fa=0; t[num].tag=t[num].rev=0; t[num].size=1; t[num].sum=t[num].w=t[num].lmax=t[num].rmax=-inf; return num; } il void up(int x){ if(!x) return ; int ls=t[x].son[0],rs=t[x].son[1]; t[x].size=t[ls].size+t[rs].size+1; t[x].sum=t[ls].sum+t[rs].sum+t[x].w; t[x].lmax=max(t[ls].lmax,t[ls].sum+t[x].w+max(0,t[rs].lmax) ); t[x].rmax=max(t[rs].rmax,t[rs].sum+t[x].w+max(0,t[ls].rmax) ); t[x].ans=max( max(t[ls].ans,t[rs].ans),max(0,t[ls].rmax)+t[x].w+max(0,t[rs].lmax) ); } il void build_tree(RG int x,RG int l,RG int r){ RG int mid=(l+r)>>1; t[x].w=a[mid]; if(l==r){ t[x].sum=t[x].lmax=t[x].rmax=t[x].ans=t[x].w; t[x].size=1; return ; } if(l<mid){ t[x].son[0]=newnode(),t[ t[x].son[0] ].fa=x; build_tree(t[x].son[0],l,mid-1); } if(r>mid){ t[x].son[1]=newnode(),t[ t[x].son[1] ].fa=x; build_tree(t[x].son[1],mid+1,r); } up(x); } il void reverse(int x){ //翻转的副操作 if(!x) return ; swap(t[x].lmax,t[x].rmax); //!!别落下了!! swap(t[x].son[0],t[x].son[1]); t[x].rev^=1; } il void replace(int x,int v){ //修改的副操作 if(!x) return ; t[x].w=v,t[x].sum=v*t[x].size; t[x].lmax=t[x].rmax=t[x].ans=max(v,v*t[x].size); t[x].tag=1,t[x].rev=0; } il void push_down(int x){ //标记下放 if(t[x].rev){ if( t[x].son[0] ) reverse(t[x].son[0]); if( t[x].son[1] ) reverse(t[x].son[1]); t[x].rev=0; } if(t[x].tag){ if( t[x].son[0] ) replace(t[x].son[0],t[x].w); if( t[x].son[1] ) replace(t[x].son[1],t[x].w); t[x].tag=0; } } il void down(int x){ if(t[x].fa) down(t[x].fa); push_down(x); } il int get_kth(int x,int k){ //查第 k 个节点编号 push_down(x); i