左偏树

Posted by Cww97 on 2017-08-25

版权声明:本文为博主原创文章,未经博主允许不得转载。原文所在http://blog.csdn.net/cww97 https://blog.csdn.net/cww97/article/details/77584240
本文作者:czj

左偏树的一道例题,hdu 1512

题目大意:有n个猴子,一开始每个猴子只认识自己。每个猴子有一个力量值,力量值越大表示这个猴子打架越厉害。如果2个猴子不认识,他们就会找他们认识的猴子中力量最大的出来单挑,单挑不论输赢,单挑的2个猴子力量值减半,这2拨猴子就都认识了,不打不相识嘛。现在给m组询问,如果2只猴子相互认识,输出-1,否则他们各自找自己认识的最牛叉的猴子单挑,求挑完后这拨猴子力量最大值。

题目分析:首先很明显这题涉及到集合并的操作,要用到并查集。其次要找到某一拨猴子中力量最大值,找最大值最快的应该是堆。2拨猴子要快速合并而又不失堆的特性,想来想去左偏树比较合适。

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
int l,r,dis,key;
} tree[MAXN];
int far[MAXN];
int Find(int x) {
if(far[x] == x) return x;
return far[x] = Find(far[x]);
}

int merge(int a,int b)
{
if(!a)
return b;
if(!b)
return a;
if(tree[a].key < tree[b].key)//大堆
swap(a,b);
tree[a].r = merge(tree[a].r,b);
far[tree[a].r] = a;//并查
if(tree[tree[a].l].dis < tree[tree[a].r].dis)
swap(tree[a].l,tree[a].r);
if(tree[a].r)
tree[a].dis = tree[tree[a].r].dis + 1;
else
tree[a].dis = 0;
return a;
}

int pop(int a)
{
int l = tree[a].l;
int r = tree[a].r;
far[l] = l;//因为要暂时删掉根,所以左右子树先作为根
far[r] = r;
tree[a].l = tree[a].r = tree[a].dis = 0;
return merge(l,r);
}

int main()
{
int N, M;
while(cin >> N)
{

for(int i = 1; i <= N; i++)
{
int x;
far[i] = i;
scanf("%d", &x);
tree[i].key = x;
tree[i].l = tree[i].r = tree[i].dis = 0;
}
cin >> M;
while(M--) {
int x, y;
scanf("%d%d", &x, &y);
x = Find(x);
y = Find(y);
if(x == y) {
printf("-1\n");
} else {
int ra = pop(x);
tree[x].key /= 2;
ra = merge(ra, x);
int rb = pop(y);
tree[y].key /= 2;
rb = merge(rb, y);
x = merge(ra, rb);
printf("%d\n", tree[x].key);
}
}
}
return 0;
}