左偏树模板

概要：左偏树是具有左偏性质的堆有序二叉树，它相比于优先队列，能够实现合并堆的功能。

先orz国家集训队论文https://wenku.baidu.com/view/515f76e90975f46527d3e1d5.html

左偏树的几个基本性质如下：

节点的键值小于等于它的左右子节点的键值
节点的左子节点的距离不小于右子节点的距离
节点的距离等于右子节点的距离加一，由此可推出一个引理和一个定理：
1. 　　若左子树的距离为一定值，则节点数最少的左偏树是完全二叉树
2. 若一棵左偏树的距离为k，则这颗左偏树至少有2^k+1-1个节点

　　4.一棵N个节点的左偏树的距离最多为[log(N+1)]-1

左偏树的节点定义：

struct node {
    int val, lc, rc, dis, par;
} t[maxn];

View Code

初始化操作：

1 void init(int x) {
2     for (int i = 1; i <= x; i++) {
3         t[i].lc = t[i].rc = t[i].dis = 0;
4         t[i].par = i;
5     }
6 }

View Code

基本的查询双亲，是否属于同个集合：

1 int find(int x) {
2     if (t[x].par == x) return x;
3     else return t[x].par = find(t[x].par);
4 }
5 
6 bool same(int x, int y) {
7     return find(x) == find(y);
8 }

View Code

左偏树的基本操作

合并操作（事实上操作时始终把B插入A中）

　　　　函数返回的是合并后的树的根节点

　　　　首先特判是否存在空树

　　　　然后注意到左偏树我们需要保证根节点键值不大于两个子节点的键值，此处我们需要特判A、B的键值，决定swap函数的调用与否（维护性质1）

　　　　接着判断A的左右子树的距离，决定是否调用swap（维护性质2）

　　　　最后根据A右子树的距离生成A的距离（维护性质3）

 1 int unite(int x, int y) {
 2     if (x == 0)
 3         return y;
 4     if (y == 0)
 5         return x;
 6     if (t[x].val < t[y].val)
 7         swap(x, y);
 8     t[x].rc = unite(t[x].rc, y);
 9     t[t[x].rc].par = x;
10     if (t[t[x].lc].dis < t[t[x].rc].dis)
11         swap(t[x].lc, t[x].rc);
12     if (t[x].rc == 0)
13         t[x].dis = 0;
14     else
15         t[x].dis = t[t[x].rc].dis + 1;
16     return x;
17 }

View Code

　　2.插入节点

　　　　将B节点视为一棵左偏树，合并A、B即可

　　3.删除最小（大）节点

　　　　等同于合并根节点的左右子树（可能会涉及修改左右子树的父亲为自身）

1 int pop(int x) {
2     int l = t[x].lc, r = t[x].rc;
3     t[x].lc = t[x].rc = t[x].dis = 0;
4     t[l].par = l, t[r].par = r;
5     return unite(l, r);
6 }

View Code

HDU-1512

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 #include <vector>
 7 #define INF 0x3f3f3f3f
 8 #define mod 1000000007
 9 typedef long long LL;
10 using namespace std;
11 const int maxn = 1e5 + 10;
12 
13 int n, m;
14 
15 struct node {
16     int val, lc, rc, dis, par;
17 } t[maxn];
18 
19 void init(int x) {
20     for (int i = 1; i <= x; i++) {
21         t[i].lc = t[i].rc = t[i].dis = 0;
22         t[i].par = i;
23     }
24 }
25 
26 int find(int x) {
27     if (t[x].par == x) return x;
28     else return t[x].par = find(t[x].par);
29 }
30 
31 bool same(int x, int y) {
32     return find(x) == find(y);
33 }
34 
35 int unite(int x, int y) {
36     if (x == 0)
37         return y;
38     if (y == 0)
39         return x;
40     if (t[x].val < t[y].val)
41         swap(x, y);
42     t[x].rc = unite(t[x].rc, y);
43     t[t[x].rc].par = x;
44     if (t[t[x].lc].dis < t[t[x].rc].dis)
45         swap(t[x].lc, t[x].rc);
46     if (t[x].rc == 0)
47         t[x].dis = 0;
48     else
49         t[x].dis = t[t[x].rc].dis + 1;
50     return x;
51 }
52 //
53 int pop(int x) {
54     int l = t[x].lc, r = t[x].rc;
55     t[x].lc = t[x].rc = t[x].dis = 0;
56     t[l].par = l, t[r].par = r;
57     return unite(l, r);
58 }
59 
60 void solve(int x, int y) {
61     x = find(x), y = find(y);
62     t[x].val /= 2, t[y].val /= 2;
63     int xx = pop(x), yy = pop(y);
64     xx = unite(xx, x), yy = unite(yy, y);
65     xx = unite(xx, yy);
66     printf("%d
", t[xx].val);
67 }
68 
69 int main(int argc, const char * argv[]) {
70     while (~scanf("%d", &n)) {
71         init(n);
72         for (int i = 1; i <= n; i++) {
73             scanf("%d", &t[i].val);
74         }
75         scanf("%d", &m);
76         while (m--) {
77             int x, y;
78             scanf("%d%d", &x, &y);
79             if (same(x, y)) {
80                 printf("-1
");
81             } else {
82                 solve(x, y);
83             }
84         }
85     }
86     return 0;
87 }

View Code