看到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棘手的操作

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

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

终于拍出来了，错误数据

#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;
}

左偏树和斜堆效率比较：

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

• 相关文章推荐
• 全局相关文章