可并堆/左偏树

介绍

可并堆是一种特殊的最小/大堆，使得两个堆之间能用 $O(\log n)$ 的时间内进行合并。由于其形态，也叫左偏树。

定义

距离：一个节点 $x$ 的距离 dis[x] 定义为：$x$ 与其子树中最近的一个children不满（指可以插入）的叶子节点的距离。

性质

左偏树是一个最小堆，每个节点有 $0-2$ 个child，并且保证节点的值 $\leq$ 其parent。
对于每一个节点 $x$，其子树均是左偏的，定义 $lc, rc$ 分别为 $x$ 的左右child，那么有 $dis_{lc} \geq dis_{rc}$。
$dis_x = dis_{rc} + 1$。
如果一个根节点的距离为 $n$，那么这个子树至少有 $2^{n+1}-1$ 个节点（因为 $dis$ 是离最近的一个未满节点的距离，意味着距离为 $n$ 之内的所有节点都满了）。由此也可以推出，拥有 $n$ 个节点的左偏树的根节点距离是 $O(\log n)$ 的。

操作

合并 merge$(x, y)$

合并两个分别以 $x,y$ 作为根节点的左偏树，返回合并之后的根节点。

WLOG 假设 $v_x \leq v_y$。
将 $y$ 与 $x$ 的右儿子 $rc$ 进行递归合并。
如果 $x, y$ 之间有任意一个为空节点（为 $0$），那么返回 $x+y$。

• 合并后，为了保持左偏特性，检查是否有 $dis_{lc} \geq dis_{rc}$，如果没有，swap(lc, rc)，然后令 $dis_x = dis_{rc} + 1$。

复杂度：由于递归 $rc$，且 $dis_x = dis_{rc} + 1$，所以每次递归一层则 dis 减少 $1$。由于性质 $4$，最多递归 $O(\log n)$ 层。所以合并两个大小分别为 $n,m$ 的堆的复杂度为 $O(\log n + \log m)$。

插入节点 $x$

将 $x$ 看作一个包含一个元素的堆，然后用 merge 解决。

删除根节点 $x$

直接 merge(lc, rc)（合并 $x$ 的左右child节点）即可。

删除任意节点 $x$

merge(lc, rc) 后，自底向上更新 $dis$，当不满足左偏性质时交换左右儿子，当 $dis$ 无需更新时停止递归。

代码：TODO

例题

例1 洛谷P3377 【模板】左偏树/可并堆

题意

给定 $n$ 个最小堆，每个堆一开始只有一个数。有 $m$ 个操作，每个操作有两种：

$1 ~ x ~ y$：将第 $x$ 个数所在的堆和第 $y$ 个数所在的堆合并，如果第 $x$ 个数或者第 $y$ 个数已经被删除，或者这两个数已经在同一个堆内，无视此操作。

$2 ~ x$：删除第 $x$ 个数所在的堆的最小值，并且将这个最小值从堆中删除，如果已经删除则输出 $-1$ 并无视此操作。

其中，$n, m \leq 10^5$。

题解

本题需要与并查集结合，因为堆的最小值本质上是询问一个堆的根，所以每一个节点都要维护其 parent。

几个需要注意的点：

需要使用路径压缩。
merge$(x,y)$ 后，由于返回的新根一定是 $x$，所以需要让 $lc, rc$ 的 par 都设为 $x$。
del$(x)$ 时，先让左右子树断开（设 par 为它们自己），然后将它们 merge 起来。另外，由于路径压缩，尽管 $x$ 已经被删除了，但可能有其他节点的 par 指向了 $x$，所以 $x$ 的parent需要指向 merge 之后的节点。

代码

#include <bits/stdc++.h>
using namespace std;
struct MergeHeap {
    struct Node {
        int dis, val, par, lc, rc;
    } tr[maxn];
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tuple {tr[x].val, x} > tuple {tr[y].val, y}) swap(x, y);
        tr[x].rc = merge(tr[x].rc, y);
        int lc = tr[x].lc, rc = tr[x].rc;
        tr[lc].par = tr[rc].par = x;  // 注意 merge 过后，需要调整 par
        if (tr[lc].dis < tr[rc].dis) swap(tr[x].lc, tr[x].rc);
        tr[x].dis = tr[tr[x].rc].dis + 1;
        return x;
    }
    void del(int x) {
        tr[x].val = -1;  // 删除这个元素
        int lc = tr[x].lc, rc = tr[x].rc;
        tr[lc].par = lc, tr[rc].par = rc;  // 这里要先断开 (让lc和rc的par等于自己)
        tr[x].par = merge(lc, rc);  // 由于路径压缩，虽然 x 被删除了，但是其子树有可能有指向 $x$ 的
    }

    int finds(int x) {
        if (tr[x].par == x) return x;
        return tr[x].par = finds(tr[x].par);
    }
    void unions(int x, int y) {
        if (tr[x].val == -1 || tr[y].val == -1) return;  // 需要在 finds(x) 之前检查是否删除
        x = finds(x), y = finds(y);
        if (x == y) return;  // finds 之后再检查是否已经union在一起了
        merge(x, y);
    }
} tr;

int n, m;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> tr.tr[i].val, tr.tr[i].par = i;  // 注意初始化 par
    while (m--) {
        int op; cin >> op;
        if (op == 1) {
            int x, y; cin >> x >> y;
            tr.unions(x, y);
        } else {
            int x; cin >> x;
            if (tr.tr[x].val == -1) cout << -1 << "\n";
            else {
                x = tr.finds(x);
                cout << tr.tr[x].val << "\n";
                tr.del(x);
            }
        }
    }
}

例2 洛谷P1456 Monkey King

题意

有 $n$ 个猴子，每个猴子有一个强壮值。

一开始每个猴子互不认识。有 $m$ 次决斗，每次决斗发生时，两个猴子所认识的所有猴子中最强的会参战，参战后其强壮值会减半。并且每次决斗后，两方的所有猴子都会互相认识了。

对于每次决斗，输出决斗后，它们认识中的所有猴子的最大的强壮值。

其中，$n, m \leq 10^5$。

题解

和上一题一样，只不过这次有一个 decrease-key 的操作，其实就相当于删除，再加入即可。

不过区别在于，这个删除并不是真的删除了，它只不过是value减半了而已，所以不需要调用之前的 del(x)，直接再merge回去就行了。

代码

#include <bits/stdc++.h>
using namespace std;
struct MergeHeap {
    struct Node {
        int dis, val, par, lc, rc;
    } tr[maxn];
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (tuple {tr[x].val, x} < tuple {tr[y].val, y}) swap(x, y);
        tr[x].rc = merge(tr[x].rc, y);
        int lc = tr[x].lc, rc = tr[x].rc;
        tr[lc].par = tr[rc].par = x;  // 调整 lc, rc 的parent
        if (tr[lc].dis < tr[rc].dis) swap(tr[x].lc, tr[x].rc);
        tr[x].dis = tr[tr[x].rc].dis + 1;
        return x;
    }
    int finds(int x) {
        if (tr[x].par == x) return x;
        return tr[x].par = finds(tr[x].par);
    }
    int decrease(int x) {
        tr[x].val /= 2;
        int lc = tr[x].lc, rc = tr[x].rc;
        int rt = merge(lc, rc);
        tr[x] = {0, tr[x].val, 0, 0, 0};
        tr[x].par = tr[rt].par = merge(x, rt);
        return tr[rt].par;
    }
} tr;

int n, m;
int main() {
    while (cin >> n) {
        for (int i = 1; i <= n; i++) {
            tr.tr[i] = {0, 0, 0, 0, 0};
            cin >> tr.tr[i].val, tr.tr[i].par = i;
        }
        cin >> m;
        while (m--) {
            int x, y; cin >> x >> y;
            x = tr.finds(x), y = tr.finds(y);
            if (x == y) cout << -1 << "\n";
            else {
                x = tr.decrease(x); y = tr.decrease(y);
                tr.merge(x, y);
                cout << tr.tr[tr.finds(x)].val << "\n";
            }
        }
    }
}

例3 洛谷P1552 [APIO2012] 派遣

题意

给定 $n$ 个人，这 $n$ 个人形成了一棵树，每个人有一个工资 $c_i$，以及领导力 $L_i$。

现在总预算有 $m$，我们需要选择一个人 $x$ 作为领导，并且从它的子树内选中一些人，使得这些人的工资总和 $\leq m$，需要最大化 $L_x * sz$，其中 $sz$ 是被选中的人的数量。

求出这个最大值。

其中，$n \leq 10^5, m, c_i, L_i \in [1,10^9]$。

题解

不难发现，枚举每一个可能的领导，然后保留他手下所有工资最低的人即可。

所以对于每棵子树，维护一个最大堆，当堆内的工资和 $> m$ 时，就pop掉。因为被pop掉后一定不会再被考虑进去，所以这样做是对的。

用可并堆，将 $x$ 与它的所有子树的堆合并在一起，递归解决即可。

• 对于本题，删除一个节点后，unions(u,v) 不能直接跳过，因为一个子树被删除的节点有可能是这个子树的根，所以还是需要先 finds(u)，然后再merge。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const int maxm = 2e7+500;

vector<int> adj[maxn];
ll cost[maxn];  // 节点本身的 cost
struct MergeHeap {
    struct Node {
        int dis, val, par, lc, rc, sz;
        ll cost, L;  // cost 的和
    } tr[maxn];
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (cost[x] < cost[y] || (cost[x] == cost[y] && x < y)) swap(x, y);  // 这里不要比较错了
        tr[x].rc = merge(tr[x].rc, y);
        int lc = tr[x].lc, rc = tr[x].rc;
        if (tr[lc].dis < tr[rc].dis) swap(tr[x].lc, tr[x].rc);

        tr[lc].par = tr[rc].par = x;  // 注意 merge 过后，需要调整 par
        tr[x].sz = tr[lc].sz + tr[rc].sz + 1;
        tr[x].cost = tr[lc].cost + tr[rc].cost + cost[x];
        tr[x].dis = tr[tr[x].rc].dis + 1;
        return x;
    }
    void del(int x) {
        tr[x].val = -1;  // 删除这个元素
        int lc = tr[x].lc, rc = tr[x].rc;
        tr[lc].par = lc, tr[rc].par = rc;  // 这里要先断开 (让lc和rc的par等于自己)
        tr[x].par = merge(lc, rc);  // 由于路径压缩，虽然 x 被删除了，但是其子树有可能有指向 $x$ 的
    }

    int finds(int x) {
        if (tr[x].par == x) return x;
        return tr[x].par = finds(tr[x].par);
    }
    void unions(int x, int y) {
        // if (tr[x].val == -1 || tr[y].val == -1) return;  // 需要在 finds(x) 之前检查是否删除
        x = finds(x), y = finds(y);
        if (x == y) return;  // finds 之后再检查是否已经union在一起了
        merge(x, y);
    }
} tr;

int n, m;
ll ans = 0;
void dfs(int u, int p) {
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        tr.unions(u, v);
    }
    int rt = tr.finds(u);
    while (tr.tr[rt].cost > m) {
        tr.del(rt);
        rt = tr.finds(u);
    }
    rt = tr.finds(u);
    ans = max(ans, tr.tr[rt].sz * tr.tr[u].L);
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
        adj[i].push_back(p);
        cin >> cost[i] >> tr.tr[i].L;
        tr.tr[i].par = i;  // 注意初始化 par
        tr.tr[i].sz = 1;
        tr.tr[i].cost = cost[i];
    } 
    dfs(1, 0);
    cout << ans << endl;
}

例4 洛谷P3273 [SCOI2011] 棘手的操作

题意

有 $N$ 个节点，标号从 $1$ 到 $N$，这 $N$ 个节点一开始相互不连通。第 $i$ 个节点的初始权值为 $a_i$，有 $m$ 个如下操作：

$U ~x ~y$: 加一条边，连接第 $x$ 个节点和第 $y$ 个节点

$A_1 ~x ~v$: 将第 $x$ 个节点的权值增加 $v$

$A_2 ~x ~v$: 将第 $x$ 个节点所在的连通块的所有节点的权值都增加 $v$

$A_3 ~v$: 将所有节点的权值都增加 $v$

$F_1 ~x$: 输出第 $x$ 个节点当前的权值

$F_2 ~x$: 输出第 $x$ 个节点所在的连通块中，权值最大的节点的权值

$F_3$: 输出所有节点中，权值最大的节点的权值

其中，$n, m \leq 3\times 10^5, v, a_i \in [-1000,1000]$。

题解

虽然可并堆可做，但做起来太阴间了，所以我们利用离线，然后用线段树来做。

怎么离线呢？

注意到我们唯一的连接操作是链接两个联通块。那么易知存在一种映射方式，将 1-n 映射到另外一个 1-n 的permutation，使得每次链接的两个联通块一定是两个相邻的区间，这也意味着在任意时刻，每个联通块都只由一个区间组成。

如何映射？

我们先把所有的 U x y 操作都拿出来，用并查集模拟这个链接过程，用链表来维护。

在初始情况下，每个节点都是一个链表，在并查集链接时，将两个链表接在一起，这样就保证了每次链接后，每个联通块都是一个链表。在全部链接结束后，遍历所有的链表，按照顺序给它们编号即可，如 1 -> 4 -> 2 -> 3 和 6 -> 5 这两个链表，我们就可以映射成 1 -> 2 -> 3 -> 4 和 5 -> 6。

在重新映射后，所有的询问和修改操作都变成了对一个区间进行，当然我们需要快速的找出第 $x$ 个节点所在的区间，这个在并查集的时候维护一个 L, R 即可。

时间复杂度就是 $O(n \log n)$ 了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
const int maxm = 2e5+500;

struct UnionFind {
    int n, par[maxn], L[maxn], R[maxn];
    UnionFind(int n) : n(n) {
        for (int i = 1; i <= n; i++) par[i] = i, L[i] = R[i] = i;
    }
    int finds(int u) {
        if (u == par[u]) return u;
        return par[u] = finds(par[u]);
    }
    void unions(int u, int v) {
        u = finds(u), v = finds(v);
        if (u == v) return;
        par[v] = u;
        L[u] = min(L[u], L[v]);
        R[u] = max(R[u], R[v]);
    }
};

struct LinkedList {
    int pre, nxt;
} b[maxn];

int n, a[maxn], Q;
struct Query {
    char type[2];
    int x, v;
} queries[maxn];

int ori_to_time[maxn];
void preprocess() {
    UnionFind uf = UnionFind(n);
    for (int i = 1; i <= n; i++) uf.L[i] = uf.R[i] = i, b[i].pre = b[i].nxt = i;
    for (int i = 1; i <= Q; i++) {
        int u = queries[i].x, v = queries[i].v;
        if (queries[i].type[0] != 'U') continue;
        u = uf.finds(u), v = uf.finds(v);
        if (u == v) continue;
        int utail = uf.R[u], vhead = uf.L[v];
        b[utail].nxt = vhead;
        b[vhead].pre = utail;
        uf.par[v] = u;
        uf.R[u] = uf.R[v];
    }
    int id = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i].pre == i) {
            int p = i;
            while (b[p].nxt != p) {
                ori_to_time[p] = ++id;
                p = b[p].nxt;
            }
            ori_to_time[p] = ++id;
        }
    }
}

struct SegmentTree {
    struct Node {
        int mx, tag;
    };
    Node tr[maxn<<2];
    void push_up(int cur) {
        tr[cur].mx = max(tr[cur<<1].mx, tr[cur<<1|1].mx);
    }
    void push_down(int cur, int l, int r) {
        if (!tr[cur].tag) return;
        ll tag = tr[cur].tag;
        tr[cur].tag = 0;
        int lc = cur<<1, rc = lc + 1;
        tr[lc].mx += tag;
        tr[rc].mx += tag;
        tr[lc].tag += tag;
        tr[rc].tag += tag;
    }
    void update(int cur, int l, int r, int L, int R, ll x) {
        if (L <= l && R >= r) {
            tr[cur].tag += x;
            tr[cur].mx += x;
            return;
        }
        push_down(cur, l, r);
        int mid = (l+r) >> 1;
        if (L <= mid) update(cur<<1, l, mid, L, R, x);
        if (R > mid) update(cur<<1|1, mid+1, r, L, R, x);
        push_up(cur);
    }
    ll query(int cur, int l, int r, int L, int R) {
        if (l >= L && r <= R) return tr[cur].mx;
        push_down(cur, l, r);
        int mid = (l+r) >> 1;
        ll res = -1e18;
        if (L <= mid) res = max(res, query(cur<<1, l, mid, L, R));
        if (R > mid) res = max(res, query(cur<<1|1, mid+1, r, L, R));
        push_up(cur);
        return res;
    }
    void build(int cur, int l, int r) {
        if (l == r) {
            tr[cur].mx = a[l];
            return;
        }
        int mid = (l+r) >> 1;
        build(cur<<1, l, mid);
        build(cur<<1|1, mid+1, r);
        push_up(cur);
    }
} tr;


int FLAG = 0;
ll MX = -1e18;
int ttmp[maxn];
int main() {
    fastio;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> Q;

    for (int i = 1; i <= Q; i++) {
        string tmp; cin >> tmp;
        queries[i].type[0] = tmp[0];
        if (tmp.size() > 1) queries[i].type[1] = tmp[1];
        if (queries[i].type[0] == 'U') {
            int x, y; cin >> x >> y;
            queries[i].x = x, queries[i].v = y;
        } else {
            if (queries[i].type[0] == 'A' && queries[i].type[1] <= '2') cin >> queries[i].x >> queries[i].v;
            if (queries[i].type[0] == 'A' && queries[i].type[1] == '3') cin >> queries[i].v;
            if (queries[i].type[0] == 'F' && queries[i].type[1] <= '2') cin >> queries[i].x;
        }
    }
    preprocess();

    for (int i = 1; i <= n; i++) ttmp[i] = a[i];
    for (int i = 1; i <= n; i++) a[ori_to_time[i]] = ttmp[i];
    UnionFind uf = UnionFind(n);
    tr.build(1, 1, n);
    MX = tr.query(1, 1, n, 1, n);

    for (int i = 1; i <= Q; i++) {
        char* type = queries[i].type;
        int x = queries[i].x, v = queries[i].v;
        x = ori_to_time[x];
        if (type[0] == 'U') {
            uf.unions(x, ori_to_time[v]);
        } 
        if (type[0] == 'A' && type[1] == '1') {
            tr.update(1, 1, n, x, x, v);
            MX = tr.query(1, 1, n, 1, n);
        }
        if (type[0] == 'A' && type[1] == '2') {
            x = uf.finds(x);
            int L = uf.L[x], R = uf.R[x];
            tr.update(1, 1, n, L, R, v);
            MX = tr.query(1, 1, n, 1, n);
        }
        if (type[0] == 'A' && type[1] == '3') {
            FLAG += v;
        }
        if (type[0] == 'F' && type[1] == '1') {
            cout << tr.query(1, 1, n, x, x) + FLAG << "\n";
        }
        if (type[0] == 'F' && type[1] == '2') {
            x = uf.finds(x);
            int L = uf.L[x], R = uf.R[x];
            cout << tr.query(1, 1, n, L, R) + FLAG << "\n";
        }
        if (type[0] == 'F' && type[1] == '3') {
            cout << MX + FLAG << "\n";
        }
    }
}