可并堆就是可以快速合并的堆，可用左偏树来实现。

左偏树

        二叉堆，这是一个很熟悉的数据结构。但是如何将两个二叉堆合并起来？STL中的优先队列并没有提供这个方法，手写堆合并复杂度达到$O(nlogn)$，效率很低。左偏树可以在对数时间复杂度下完成合并操作。
        首先认识左偏树的性质，以小根堆为例。
        定义距离的概念：外结点（左儿子或右儿子为空的结点）距离定义为0，其余结点距离定义为该点到离它最近的叶子结点的距离（就是边的数量）。左偏树满足：

  • 【堆性质】任意结点的权值必不大于其两个子结点的权值。
  • 【左偏性质】任意结点左儿子的距离必不小于右儿子

        左偏树不再是完全二叉树，但仍是二叉树，满足堆的性质。
        这样可以得到两个推论：

  • 任意结点距离为其右儿子距离加一
  • 有n个结点的左偏树，其最大距离为$log(n+1)-1$。

        关于第二个推论的证明：假定最大距离为d，那么结点数最少时就是完全二叉树的情况，即有$n\geq 2^{d+1}-1$，那么有$d\leq log(n+1)-1$。
        第二个推论保证了左偏树的时间复杂度。
        如何合并呢？这个过程类似FHQ Treap的合并过程，以递归的方式进行。
        假设要合并以a和b为根的两棵左偏树，如果a结点的权值更大，那么交换两棵树。这一步是为了使a结点作为新树的根。
        这时结点a必为根，此时合并树a的右儿子（这里合并左儿子也是可以的）和树b，递归进行。将合并后的新树根作为右儿子（左儿子）。根据左偏树推论二，这一步合并的时间复杂度在对数级别。这一步之后，左偏树的性质可能会被破坏，需要调整左右子树位置，更新距离。代码如下：

1
2
3
4
5
6
7
8
9
int merge(int a, int b) {
    if (!a || !b)return a + b;
    if (val[root[a].d] > val[root[b].d] || (val[root[a].d] == val[root[b].d] && root[a].d > root[b].d))swap(a, b);
    int p = merge(root[a].ch[0], b);
    father[p] = a, root[a].ch[0] = p;//father是并查集使用的，暂且不用管它
    if (root[root[a].ch[0]].dict < root[root[b].ch[1]].dict)swap(root[a].ch[0], root[a].ch[1]);
    root[a].dict = root[root[a].ch[1]].dict + 1;
    return a;
}

        为什么不直接用二叉堆进行上面的过程呢？这是由于二叉堆是完全二叉树，合并后很难再去维护它的结构。左偏树一方面结构比较灵活，另一方面还可以保证时间复杂度，于是可以很好地实现堆的合并。
        左偏树的插入操作就是将左偏树和一棵只有一个结点的左偏树合并，删除最小值只需删掉最小值结点再合并两棵子树即可。这些都是容易实现的。
        在洛谷模板题中，结点关系需要用并查集去维护。两棵树合并就是两个并查集等价类合并，删除时重新处理父子关系即可。比如树a和树b合并，合并后树根为b，只需将a的父亲换为b即可，删除时合并两棵子树同理。这样的好处是思维难度小，但不允许路径压缩，容易被卡成$O(n)$。
        要降低时间复杂度当然就是用允许路径压缩的方法。具体区别体现在删除上。当删除一棵树的树根时，将树根（即使被删除）的父亲换为新树的树根，这样子结点就可以通过原有的树根来访问新的树根了。
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
#include<bits/stdc++.h>

#define N 100010
using namespace std;
int father[N], n, m,  val[N];

struct Node {
    int d, dict, ch[2];

    Node() {
        ch[0] = ch[1] = 0, dict = 0;
    }
} root[N];

int find(int x) {//并查集
    if (father[x] == x)return x;
    return father[x] = find(father[x]);//路径压缩
}

int merge(int a, int b) {//合并操作
    if (!a || !b)return a + b;
    if (val[root[a].d] > val[root[b].d] || (val[root[a].d] == val[root[b].d] && root[a].d > root[b].d))swap(a, b);
    int p = merge(root[a].ch[1], b);
    father[p] = a, root[a].ch[1] = p;
    if (root[root[a].ch[0]].dict < root[root[a].ch[1]].dict)swap(root[a].ch[0], root[a].ch[1]);
    root[a].dict = root[root[a].ch[1]].dict + 1;
    return a;
}

int pop(int a) {//删除操作
    int t = val[a];
    father[root[a].ch[1]] = root[a].ch[1], father[root[a].ch[0]] = root[a].ch[0];//两棵子树独立
    father[a] = merge(root[a].ch[0], root[a].ch[1]), val[a] = -1;//修改旧树根父子关系
    return t;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    root->dict = -1;
    for (int i = 1; i <= n; i++)cin >> val[i], root[i].d = i, father[i] = i;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a;
        if (a == 1) {
            cin >> b >> c;
            if (val[b] == -1 || val[c] == -1 || find(b) == find(c))continue;
            merge(find(b), find(c));
        } else {
            cin >> b;
            if (val[b] == -1)cout << -1 << endl;
            else cout << pop(find(b)) << endl;
        }
    }
    return 0;
}

代码模板

        上面的代码和模板题联系太紧密，这里给出一个比较独立的板子：

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
#include<bits/stdc++.h>

#define N 100010
using namespace std;

struct Node {
    int dict, ch[2], v;
} nd[N];

inline int newNode(int x) {//分配一个新结点
    static int cnt = 1;
    nd[cnt].v = x;
    return cnt++;
}

int merge(int a, int b) {//合并两个堆
    if (!a || !b)return a + b;
    if (nd[a].v > nd[b].v)swap(a, b);
    int p = merge(nd[a].ch[1], b);
    nd[a].ch[1] = p;
    if (nd[nd[a].ch[0]].dict < nd[nd[a].ch[1]].dict)swap(nd[a].ch[0], nd[a].ch[1]);
    nd[a].dict = nd[nd[a].ch[1]].dict + 1;
    return a;
}

void pop(int &x) {//删除一个堆的首结点
    x = merge(nd[x].ch[0], nd[x].ch[1]);
}

int main() {
  	//做些什么...
}

例题

        下面给出一些例题，不涉及题面，点击标题可跳转。

Monkey King

        很裸的左偏树，稍微需要动点脑子的地方是如何快速求某一个结点所在堆的根结点，这个可以用并查集+路径压缩快速求得，具体见代码。
        这种维护结点所在堆的根结点方法很常用，可以套在许多左偏树题目中。

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
#include<bits/stdc++.h>
#include <assert.h>

#define N 100010
using namespace std;

struct Node {
    int dict, ch[2], v;
} nd[N];
int cnt = 1, fa[N], n, m;

inline int newNode(int x) {
    nd[cnt].v = x, nd[cnt].ch[0] = nd[cnt].ch[1] = nd[cnt].dict = 0;
    return cnt++;
}

int findF(int x) {
    return fa[x] == x ? x : fa[x] = findF(fa[x]);
}

int merge(int a, int b) {
    if (!a || !b)return a + b;
    if (nd[a].v < nd[b].v)swap(a, b);
    int p = merge(nd[a].ch[1], b);
    nd[a].ch[1] = p;
    if (nd[nd[a].ch[0]].dict < nd[nd[a].ch[1]].dict)swap(nd[a].ch[0], nd[a].ch[1]);
    nd[a].dict = nd[nd[a].ch[1]].dict + 1;
    return a;
}

void pop(int &x) {
    x = merge(nd[x].ch[0], nd[x].ch[1]);
}

int main() {
    while (scanf("%d", &n) != EOF) {
        cnt = 1;
        for (int i = 1, x; i <= n; i++)scanf("%d", &x), newNode(x), fa[i] = i;
        scanf("%d", &m);
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            if (findF(x) == findF(y))printf("-1\n");
            else {
                int a = findF(x), b = findF(y), c, aa = a, bb = b;
                pop(a), pop(b), c = merge(a, b);
                nd[aa].v >>= 1, nd[bb].v >>= 1;
                nd[aa].ch[0] = nd[aa].ch[1] = 0;//注意清空子结点
                nd[bb].ch[0] = nd[bb].ch[1] = 0;
                c = merge(aa, c), c = merge(bb, c);
                printf("%d\n", nd[c].v);
                fa[aa] = fa[bb] = c, fa[c] = c;
            }
        }
    }
    return 0;
}

[JLOI2015]城池攻占

        $O(nm)$暴力很容易想，但是必然TLE，其实本题可以用左偏树优雅地切掉。
        我们用一个小跟堆储存树上每一个结点的骑士信息，弹出小于自身防御力的骑士，剩下的就是可以攻占该结点的骑士。由于骑士会从子结点移动到该结点，故需要合并子结点的堆，这里就需要左偏树。
        更新堆中的数据时，我们发现加上一个数并不会影响堆中数的相对大小关系，同样乘上一个正数也不会影响，这使得我们可以在不改变堆原有结构的前提下完成堆的合并。至于如何乘上或加上一个数，打懒标记即可，这里可以参考线段树一文的进阶部分。

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>

#define N 300010
using namespace std;

struct Node {
    int dict, ch[2], la_qs, num;
    long long v, la_plus, la_times;
} nd[N];

struct Edge {
    int next, to;
} edge[N << 1];
int head[N], root[N], n, m, a[N], ans[N];
long long hp[N], v[N];

inline int newNode(long long x) {
    static int cnt = 1;
    nd[cnt].la_times = 1, nd[cnt].v = x;
    return cnt++;
}

inline void add(int x, int y) {
    static int c = 1;
    edge[c].to = y, edge[c].next = head[x], head[x] = c++;
}

inline void down(int x) {
    if (nd[x].la_times != 1) {
        nd[nd[x].ch[0]].v *= nd[x].la_times;
        nd[nd[x].ch[1]].v *= nd[x].la_times;
        nd[nd[x].ch[0]].la_times *= nd[x].la_times;
        nd[nd[x].ch[1]].la_times *= nd[x].la_times;
        nd[nd[x].ch[0]].la_plus *= nd[x].la_times;
        nd[nd[x].ch[1]].la_plus *= nd[x].la_times;
        nd[x].la_times = 1;
    }
    if (nd[x].la_plus) {
        nd[nd[x].ch[0]].v += nd[x].la_plus;
        nd[nd[x].ch[1]].v += nd[x].la_plus;
        nd[nd[x].ch[0]].la_plus += nd[x].la_plus;
        nd[nd[x].ch[1]].la_plus += nd[x].la_plus;
        nd[x].la_plus = 0;
    }
    if (nd[x].la_qs) {
        nd[nd[x].ch[0]].num += nd[x].la_qs;
        nd[nd[x].ch[1]].num += nd[x].la_qs;
        nd[nd[x].ch[0]].la_qs += nd[x].la_qs;
        nd[nd[x].ch[1]].la_qs += nd[x].la_qs;
        nd[x].la_qs = 0;
    }
}

int merge(int a, int b) {
    if (!a || !b)return a + b;
    if (nd[a].v > nd[b].v)swap(a, b);
    down(a), down(b);
    int p = merge(nd[a].ch[1], b);
    nd[a].ch[1] = p;
    if (nd[nd[a].ch[0]].dict < nd[nd[a].ch[1]].dict)swap(nd[a].ch[0], nd[a].ch[1]);
    nd[a].dict = nd[nd[a].ch[1]].dict + 1;
    return a;
}

void pop(int &x) {
    down(x), x = merge(nd[x].ch[0], nd[x].ch[1]);
}

void DFS(int x) {
    for (int i = head[x]; i; i = edge[i].next)DFS(edge[i].to), root[x] = merge(root[x], root[edge[i].to]);
    while (root[x] && nd[root[x]].v < hp[x])pop(root[x]), ++ans[x];
    if (root[x]) {
        if (a[x])nd[root[x]].v *= v[x], nd[root[x]].la_times *= v[x], nd[root[x]].la_plus *= v[x];
        else nd[root[x]].v += v[x], nd[root[x]].la_plus += v[x];
        ++nd[root[x]].num, ++nd[root[x]].la_qs;
    }
}

void downDFS(int x) {
    if (x == 0)return;
    down(x), downDFS(nd[x].ch[0]), downDFS(nd[x].ch[1]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%lld", hp + i);
    for (int i = 2, x; i <= n; i++)scanf("%d%d%lld", &x, a + i, v + i), add(x, i);
    for (int i = 1, to; i <= m; i++) {
        long long s;
        scanf("%lld%d", &s, &to), root[to] = merge(root[to], newNode(s));
    }
    DFS(1), downDFS(root[1]);
    for (int i = 1; i <= n; i++)printf("%d\n", ans[i]);
    for (int i = 1; i <= m; i++)printf("%d\n", nd[i].num);
    return 0;
}

[APIO2012]派遣

        也算裸题吧。
        起初每一个结点都是一个独立的堆，然后将它们向上合并到父结点，按薪水建立大根堆，并维护其中的薪水总和。不断地弹出薪水最多的结点，直到总和不超过预算，然后一直向上合并。其实这就是个贪心的思路，复杂度$O(nlogn)$。
        好像也可以用启发式合并平衡树做？不过那样要多一个log。

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
#include<bits/stdc++.h>

#define N 100010
using namespace std;

struct Node {
    int dict, ch[2], v, num;
    long long sum;
} nd[N];
int to[N], in[N], ld[N], xs[N], tr[N], n, m;
long long ans;
queue<int> que;

inline int newNode(int m) {
    static int cnt = 1;
    nd[cnt].sum = nd[cnt].v = m, nd[cnt].num = 1;
    return cnt++;
}

int merge(int a, int b) {
    if (!a || !b)return a + b;
    if (nd[a].v < nd[b].v)swap(a, b);
    int p = merge(nd[a].ch[1], b);
    nd[a].ch[1] = p;
    if (nd[nd[a].ch[0]].dict < nd[nd[a].ch[1]].dict)swap(nd[a].ch[0], nd[a].ch[1]);
    nd[a].dict = nd[nd[a].ch[1]].dict + 1, nd[a].sum = nd[nd[a].ch[0]].sum + nd[nd[a].ch[1]].sum + nd[a].v;
    nd[a].num = nd[nd[a].ch[0]].num + nd[nd[a].ch[1]].num + 1;
    return a;
}

void pop(int &x) {
    x = merge(nd[x].ch[0], nd[x].ch[1]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)scanf("%d%d%d", to + i, xs + i, ld + i), ++in[to[i]];
    for (int i = 1; i <= n; i++)if (in[i] == 0)que.push(i);
    while (!que.empty()) {
        int f = que.front();
        que.pop();
        if (f == 0)continue;
        tr[f] = merge(tr[f], newNode(xs[f]));
        while (nd[tr[f]].sum > m)pop(tr[f]);
        ans = max(ans, 1ll * ld[f] * nd[tr[f]].num);
        tr[to[f]] = merge(tr[to[f]], tr[f]), --in[to[f]];
        if (in[to[f]] == 0)que.push(to[f]);
    }
    printf("%lld", ans);
    return 0;
}