[BZOJ1500][NOI2005]维修数列 解题报告 Splay
2018-06-17 22:09:33来源:未知 阅读 ()
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);
if(t[ t[x].son[0] ].size==k-1) return x;
if(t[ t[x].son[0] ].size>k-1) return get_kth(t[x].son[0],k);
else return get_kth(t[x].son[1],k-t[ t[x].son[0] ].size-1);
}
il int dir(int x){ return x==t[ t[x].fa ].son[1]; }
il void rotate(int x){
int y,z,a,b,c;
y=t[x].fa,z=t[y].fa; b=dir(x),a=t[x].son[!b];
if(z==0) root=x;
else{ c=dir(y),t[z].son[c]=x; }
t[x].fa=z,t[y].fa=x,t[x].son[!b]=y,t[y].son[b]=a;
if(a) t[a].fa=y;
up(y),up(x);
}
il void splay(int x,int goal){
down(x);
int y,z,b,c;
while(t[x].fa!=goal){
y=t[x].fa,z=t[y].fa;
if(z==goal) rotate(x);
else{
b=dir(x),c=dir(y);
if(b^c){ rotate(x),rotate(x); }
else{ rotate(y),rotate(x); }
}
}
}
il void INSERT(int pos,int tot){ //插入
for(RG int i=1;i<=tot;i++) a[i]=gi();
int x=get_kth(root,pos+1); splay(x,0);
int y=get_kth(t[x].son[1],1); splay(y,x);
t[y].son[0]=newnode(); t[ t[y].son[0] ].fa=y;
build_tree(t[y].son[0],1,tot);
up(y),up(x);
}
il void erase(int x){ //删除的副操作
if(!x) return ; sta[++top]=x;//回收节点
if(t[x].son[0]) erase(t[x].son[0]);
if(t[x].son[1]) erase(t[x].son[1]);
}
il void DELETE(int pos,int tot){ //删除
int x=get_kth(root,pos); splay(x,0);
int y=get_kth(t[x].son[1],tot+1); splay(y,x);
erase( t[y].son[0] );
t[ t[y].son[0] ].fa=0,t[y].son[0]=0;
up(y),up(x);
}
il void MAKE_SAME(int pos,int tot,int v){ //修改
int x=get_kth(root,pos); splay(x,0);
int y=get_kth(t[x].son[1],tot+1); splay(y,x);
replace(t[y].son[0],v);
up(y),up(x);
}
il void REVERSE(int pos,int tot){ //翻转
int x=get_kth(root,pos); splay(x,0);
int y=get_kth(t[x].son[1],tot+1); splay(y,x);
reverse(t[y].son[0]);
up(y),up(x);
}
il int QUERY(int pos,int tot){ //查询
int x=get_kth(root,pos); splay(x,0);
int y=get_kth(t[x].son[1],tot+1); splay(y,x);
return t[t[y].son[0]].sum;
}
il void init(){
t[0].lmax=t[0].rmax=t[0].ans=-inf;
cnt=2,root=1; //t[1],t[2]用来防止一开始建树时超出边界
t[1].fa=0,t[1].size=2,t[1].son[1]=2,t[1].w=t[1].sum=t[1].lmax=t[1].rmax=-inf;
t[2].fa=1,t[2].size=1,t[2].w=t[2].sum=t[2].lmax=t[2].rmax=-inf;
n=gi(),Q=gi();
for(RG int i=1;i<=n;i++) a[i]=gi();
t[2].son[0]=newnode(),t[t[2].son[0]].fa=2;
build_tree(t[2].son[0],1,n); up(2),up(1);
}
il void work(){
int x,y,z; char s[15];
while(Q--){
scanf("%s",s);
if(s[0]=='I'){ x=gi(),y=gi(); INSERT(x,y); }
if(s[0]=='D'){ x=gi(),y=gi(); DELETE(x,y); }
if(s[4]=='-'){ x=gi(),y=gi(),z=gi(); MAKE_SAME(x,y,z); }
if(s[0]=='R'){ x=gi(),y=gi(); REVERSE(x,y); }
if(s[0]=='G'){ x=gi(),y=gi(); printf("%d\n",QUERY(x,y)); }
if(s[2]=='X') printf("%d\n",t[root].ans);
}
}
int main(){ init(); work(); return 0; }//贯彻一行 main() 风格
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- BZOJ1202: [HNOI2005]狡猾的商人(带权并查集) 2018-07-13
- bzoj1202 [ HNOI2005 ] --带权并查集+前缀和 2018-06-27
- bzoj1202 [ HNOI2005 ] --带权并查集+前缀和 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash