Hdu 1512(可并堆)

Hdu 1512
左偏树模板题,细节一定要注意

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
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ms(i,j) memset(i,j,sizeof i);
using namespace std;
const int MAXN = 100000 + 5;
struct node
{
int l, r;//左偏树左、右孩子编号
int dis, key;//左偏树距离,键值
int f;//并查集father
}lt[MAXN];
int n;
int m;
int find(int x) //并查集find
{
return (x==lt[x].f) ? (x) : (lt[x].f = find(lt[x].f));
}
void build(int rt, int v)//使rt初始化为v值
{
lt[rt].l = lt[rt].r = lt[rt].dis = 0;
lt[rt].key = v; lt[rt].f = rt;
if (rt==0) lt[rt].dis = -1;
}
int merge(int rtA, int rtB)//合并两棵树
{
if (rtA==0) return rtB;
if (rtB==0) return rtA;
if (lt[rtA].key<lt[rtB].key) swap(rtA, rtB);//大值左偏树要满足key(x)<key(parents[x])
lt[rtA].r = merge(lt[rtA].r, rtB);//A的右子树和B合并
int &l = lt[rtA].l, &r = lt[rtA].r;//利用引用减少代码量,更加清晰
lt[l].f = lt[r].f = rtA; //更新并查集
if (lt[l].dis<lt[r].dis) swap(l, r);//需要满足左偏性质dis(lc)>=dis(rc)
if (r==0) lt[rtA].dis = 0; else lt[rtA].dis = lt[r].dis+1;//算距离
return rtA;
}
int del(int rt)//删除rt节点
{
int l = lt[rt].l;
int r = lt[rt].r;
lt[l].f = l;
lt[r].f = r;
lt[rt].l = lt[rt].r = lt[rt].dis = 0;
return merge(l, r);
}
int main()
{
while (scanf("%d", &n)==1)
{
for (int i=1;i<=n;i++)
{
int x;
scanf("%d", &x);
build(i, x);
}
build(0, 0);
scanf("%d", &m);
for (int i=1;i<=m;i++)
{
int x,y;
scanf("%d%d", &x, &y);
int x1 = find(x);
int x2 = find(y);//找最强壮的
if (x1==x2) {printf("-1\n");continue;}
lt[x1].key>>=1;
lt[x2].key>>=1;//之后插入的值
int left = del(x1), right = del(x2);
left = merge(left, x1), right = merge(right, x2);
left = merge(left, right);
printf("%d\n", lt[left].key);
}
}
fclose(stdin);fclose(stdout);
return 0;
}
------ 本文结束 ------