可并堆

orz hhw posted @ 2015年5月10日 15:27 in 算法学习 with tags 数据结构 模板 bzoj 左偏树 斜堆 算法学习 可并堆 , 771 阅读

看到BZOJ2809做对的人挺多,想了一会感觉要写Splay什么的,代码不可能只有1KB,就看了看标算,发现并深深爱上了这个算法

然后就阅读了《左偏树的特点及其应用》,自己写了模板,做了一道模板题HDOJ1512,然后就要回寝室了,第二天选修课上把BZOJ2809写了出来

 

合并操作

int merge(int x,int y){
	if(!x)return y;//只剩某一子数(点)的情况 
	if(!y)return x;
	if(val[x]<val[y])swap(x,y);//以x为最大点
	son[x][1]=merge(son[x][1],y);
	father[son[x][1]]=x; 
	if(dis[son[x][1]]>dis[son[x][0]])swap(son[x][0],son[x][1]);//维护左偏树性质
	if(!son[x][1])dis[x]=0;else dis[x]=dis[son[x][1]]+1;//左偏树性质
	return x;
}

HDOJ1512

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 222222
using namespace std;
int n,i,m,x,y,p,q,xx,yy,father[N],dis[N],val[N],son[N][2];
int find(int &x){if(father[x]!=x)father[x]=find(father[x]);return father[x];}
int merge(int x,int y){
	if(!x)return y;//只剩某一子数(点)的情况 
	if(!y)return x;
	if(val[x]<val[y])swap(x,y);//以x为最大点
	son[x][1]=merge(son[x][1],y);
	father[son[x][1]]=x; 
	if(dis[son[x][1]]>dis[son[x][0]])swap(son[x][0],son[x][1]);//维护左偏树性质
	if(!son[x][1])dis[x]=0;else dis[x]=dis[son[x][1]]+1;//左偏树性质
	return x;
}
int pop(int &x){//弹出最大值并删除 
	int l=son[x][0],r=son[x][1];
	father[l]=l;father[r]=r;
	son[x][0]=son[x][1]=dis[x]=0;
	return merge(l,r);
}
int main(){
	while(scanf("%d",&n)!=EOF){
		for(i=1;i<=n;i++){
			scanf("%d",&val[i]);
			son[i][0]=son[i][1]=dis[i]=0;
			father[i]=i;
		}
		scanf("%d",&m);
		for(i=1;i<=m;i++){
			scanf("%d%d",&x,&y);
			p=find(x);q=find(y);
			if(p!=q){
				val[p]>>=1;xx=merge(pop(p),p);//题意要求,取出组中最大值除2 
				val[q]>>=1;yy=merge(pop(q),q);
				printf("%d\n",val[merge(xx,yy)]);//输出组中最大值 
			}else puts("-1");
		}
	}
} 

BZOJ2809

#include<cstdio>
#include<iostream>
#define N 222222
using namespace std;
long long n,m,i,p,now,ans,tot,q,val[N],l[N],root[N],dis[N],son[N][2],last[N],next[N],first[N],sum[N],size[N];
bool vis[N];
void insert(long long x,long long y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
long long merge(long long x,long long y){
	if(!x)return y;
	if(!y)return x;
	if(val[x]<val[y])swap(x,y);
	son[x][1]=merge(son[x][1],y);
	root[son[x][1]]=x;
	if(dis[son[x][1]]>dis[son[x][0]])swap(son[x][1],son[x][0]);
	if(!son[x][1])dis[x]=0;else dis[x]=dis[son[x][1]]+1;
	return x;
}
void pop(long long &x){
	x=merge(son[x][0],son[x][1]);
}
void dfs(long long x){
	sum[x]=val[x];size[x]=1;
	for(long long i=first[x];i;i=next[i]){
		dfs(last[i]);
		sum[x]+=sum[last[i]];
		size[x]+=size[last[i]];
		root[x]=merge(root[last[i]],root[x]);
	}
	while(sum[x]>m)sum[x]-=val[root[x]],pop(root[x]),size[x]--;
	if(size[x]*l[x]>ans)ans=size[x]*l[x];
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%lld%lld%lld",&p,&val[i],&l[i]);
		if(p)insert(p,i),vis[i]=1;
		root[i]=i;
		dis[i]=son[i][0]=son[i][1]=0;
	}
	for(i=1;i<=n;i++)if(!vis[i])break;
	dfs(i);
	printf("%lld",ans);
}

BZOJ2333棘手的操作

 

 
 
Description
有N个节点,标号从1到N,这N个节点一开始相互不连通。第i个节点的初始权值为a[i],接下来有如下一些操作:
U x y: 加一条边,连接第x个节点和第y个节点
A1 x v: 将第x个节点的权值增加v
A2 x v: 将第x个节点所在的连通块的所有节点的权值都增加v
A3 v: 将所有节点的权值都增加v
F1 x: 输出第x个节点当前的权值
F2 x: 输出第x个节点所在的连通块中,权值最大的节点的权值
F3: 输出所有节点中,权值最大的节点的权值
Input
输入的第一行是一个整数N,代表节点个数。
接下来一行输入N个整数,a[1], a[2], …, a[N],代表N个节点的初始权值。
再下一行输入一个整数Q,代表接下来的操作数。
最后输入Q行,每行的格式如题目描述所示。
Output
对于操作F1, F2, F3,输出对应的结果,每个结果占一行。
Sample Input
3
0 0 0
8
A1 3 -20
A1 2 20
U 1 3
A2 1 10
F1 3
F2 3
A3 -10
F3
Sample Output
-10
10
10
HINT
 对于30%的数据,保证 N<=100,Q<=10000
对于80%的数据,保证 N<=100000,Q<=100000
对于100%的数据,保证 N<=300000,Q<=300000
对于所有的数据,保证输入合法,并且 -1000<=v, a[1], a[2], …, a[N]<=1000

【5月11日】写了1小时,调了1个多小时,一直WA,搞不清楚哪错了

【5月12日】对拍了一下,一直没拍出来。。。

终于拍出来了,错误数据

10
0 0 0 0 0 0 0 0 0 0 
25
A2 7 -1
A2 1 -2
U 7 1
A3 2
A1 7 -8
F1 5
F3 
F1 5
F1 1
F2 9
F1 4
F2 7
F1 2
F1 10
F2 4
F1 4
F3 
F1 6
F1 10
F2 8
F1 4
F2 3
F1 9
F2 3
F2 2
。。无语了。。把pushdown 的val[l]+=add[x]写成了val[l]+=val[x]
#include<cstdio>
#include<iostream>
#define N 666666
using namespace std;
int n,m,i,x,y,z,v,root,now,p,q,ans,val[N],val2[N],father[N],father2[N],son[N][2],son2[N][2],dis[N],dis2[N],add[N];
char s[9];
int find(int x){while(father[x])x=father[x];return x;}
int sum(int x){ans=0;while(x=father[x])ans+=add[x];return ans;}
void pushdown(int x){
	int l=son[x][0],r=son[x][1];
	add[l]+=add[x];val[l]+=add[x];
	add[r]+=add[x];val[r]+=add[x];
	add[x]=0;
}
int merge1(int x,int y){
	if(!x||!y)return x+y;
	if(val[x]<val[y])swap(x,y);
	pushdown(x);
	son[x][1]=merge1(son[x][1],y);
	father[son[x][1]]=x;
	if(dis[son[x][1]]>dis[son[x][0]])swap(son[x][0],son[x][1]);
	if(!son[x][1])dis[x]=0;else dis[x]=dis[son[x][1]]+1;
	return x;
}
int merge2(int x,int y){
	if(!x||!y)return x+y;
	if(val2[x]<val2[y])swap(x,y);
	son2[x][1]=merge2(son2[x][1],y);
	father2[son2[x][1]]=x;
	if(dis2[son2[x][1]]>dis2[son2[x][0]])swap(son2[x][0],son2[x][1]);
	if(!son2[x][1])dis2[x]=0;else dis2[x]=dis2[son2[x][1]]+1;
	return x;
}
int del1(int x){
	pushdown(x);
	int y=merge1(son[x][0],son[x][1]);
	if(son[father[x]][0]==x)son[father[x]][0]=y;else son[father[x]][1]=y;
	father[y]=father[x];
	return find(y);
}
void del2(int x){
	int y=merge2(son2[x][0],son2[x][1]);
	if(root==x)root=y;
	if(x==son2[father2[x]][0])son2[father2[x]][0]=y;else son2[father2[x]][1]=y;
	father2[y]=father2[x];
}
void newnode1(int x,int y){val[x]=y;father[x]=son[x][0]=son[x][1]=0;}
void newnode2(int x,int y){val2[x]=y;father2[x]=son2[x][0]=son2[x][1]=0;}
int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&val[i]),val2[i]=val[i],root=merge2(root,i);
	scanf("%d",&m);
	while(m--){
		scanf("%s",s);
		if(s[0]=='A'){
			if(s[1]=='1'){
				scanf("%d%d",&x,&v);
				del2(find(x));
				int y=del1(x);
				newnode1(x,val[x]+v+sum(x));
				int z=merge1(y,x);
				newnode2(z,val[z]);
				root=merge2(root,z);
			}
			else if(s[1]=='2'){
				scanf("%d%d",&x,&v);
				del2(y=find(x));
				val[y]+=v;add[y]+=v;
				newnode2(y,val[y]);
				root=merge2(root,y);
			}
			else scanf("%d",&x),now+=x;
		}else if(s[0]=='F'){
			if(s[1]=='1')scanf("%d",&x),printf("%d\n",val[x]+sum(x)+now);
			else if(s[1]=='2')scanf("%d",&x),printf("%d\n",val[find(x)]+now);
			else printf("%d\n",val2[root]+now);
		}else{
			scanf("%d%d",&x,&y);
			p=find(x);q=find(y);
			if(p!=q)if(merge1(p,q)==p)del2(q);else del2(p);
		}
	}
}

斜堆

似乎斜堆就是不管啥距离,合并后统统把左右子树交换,达到左偏效果,代码如下:

int merge(int x,int y){
	if(!x)return y;
	if(!y)return x;
	if(val[x]<val[y])swap(x,y);
	son[x][1]=merge(son[x][1],y);
	father[son[x][1]]=x; 
	swap(son[x][0],son[x][1]);
	return x;
}

左偏树和斜堆效率比较:

可见左偏树在时间上略胜一筹,但在空间开销和代码长度上不如斜堆

Avatar_small
nbdhhzh 说:
2015年5月12日 20:57

请问val[l]+=add[x]和val[l]+=add[x]有本质区别么。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter