原本想学的是左偏树，结果发现斜堆比左偏树好写一些。（其实就是懒。。。） 简单来说，左偏树是左边的节点距离必然大于等于右边节点距离，如果不符合，便将左右子树交换。 然而斜堆是无论什么情况下，只要向右子树插入节点或者树，左右子树便交换。 所以斜堆合并操作是均摊O(logn)，左偏树合并操作是严格O(logn)，也许斜堆会被丧心病狂的卡掉？。。。 然而当我发现删除指定节点这个操作中，左偏树需要不断向上更新距离，斜堆中则根本没有距离的概念，所以总体来看斜堆比左偏树的代码似乎简洁一些。 所以一下两道题我都是用斜堆写的。 具体内容可以参考黄源河的《左偏树特点及其应用》
zoj 2334 并查集+斜堆 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
int ag[maxn]={},fa[maxn]={},l[maxn]={},r[maxn]={};
int t[maxn]={};
int n,m,x,y;
int merge(int x,int y)
{
if(x==0) return y;
if(y==0) return x;
if(ag[x]<ag[y]) swap(x,y);
r[x]=merge(r[x],y);
swap(l[x],r[x]);
return x;
}
int deletmin(int x)
{
ag[x]/=2;
int k=x;
x=merge(l[x],r[x]);
l[k]=0; r[k]=0;
return merge(k,x);
}
int ff(int x)
{
if(fa[x]==x) return x;
fa[x]=ff(fa[x]);
t[x]=t[fa[x]];
return fa[x];
}
int main()
{
while(cin>>n){
memset(l,0,sizeof(l)); memset(r,0,sizeof(r));
for(int i=1;i<=n;i++) {scanf("%d",&ag[i]); fa[i]=i; t[i]=i;}
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
x=ff(x); y=ff(y);
if(x==y)
{
printf("-1\n"); continue;
}
t[x]=deletmin(t[x]); t[y]=deletmin(t[y]);
fa[x]=y;
t[y]=merge(t[x],t[y]);
printf("%d\n",ag[t[y]]);
}
}
return 0;
}
zoj 3512 论文中的例题，整体思路还是挺难的 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
using namespace std;
int a[maxn]={},r[maxn]={},l[maxn]={};
int n,m,num;
int t[maxn]={},b[maxn]={},shu[maxn]={};
int merge(int x,int y)
{
if(x==0) return y;
if(y==0) return x;
if(a[x]<a[y]) swap(x,y);
r[x]=merge(r[x],y);
swap(l[x],r[x]);
return x;
}
int deletemin(int x)
{
return merge(l[x],r[x]);
}
int main()
{
a[0]=-2147483644;
while(1)
{
scanf("%d",&n);
if(n==0) break;
num=0; memset(l,0,sizeof(l)); memset(r,0,sizeof(r));
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
num++; t[num]=i; b[num]=i; shu[num]=1;
while(a[t[num-1]]]]><![CDATA[>a[t[num]])
{
num--;
t[num]=merge(t[num],t[num+1]);
b[num]=b[num+1];
shu[num]+=shu[num+1];
m=b[num]-b[num-1];
m/=2; m++;
while(shu[num]>m)
{
t[num]=deletemin(t[num]);
shu[num]--;
}
}
}
long long ans=0;
for(int i=1;i<=num;i++)
{
for(int j=b[i-1]+1;j<=b[i];j++)
{
ans+=abs(a[j]-a[t[i]]);
}
}
printf("%ld\n",ans);
}
return 0;
}