概述

左偏树（Leftist Tree）是一种可高效合并的堆式数据结构，支持在 $O(\log n)$ 时间内完成合并操作。它以二叉树形式组织，同时维护堆序性与特殊的"左偏"结构，适用于需要频繁合并堆的场景，如任务调度、优先队列合并等。

基本定义与约定

• $val[u]$：节点 $u$ 的权值。
• $lc[u], rc[u]$：节点 $u$ 的左、右子节点。
• $dist[u]$：从节点 $u$ 到最近的"外节点"的距离。外节点指至少有一个子节点为空的节点。
• $par[u]$：节点 $u$ 的父节点，用于并查集路径压缩优化。

本文默认使用小根堆，即父节点权值不大于子节点。

核心性质

1. 堆序性质

对任意非根节点 $u$，满足：

$$ val[par[u]] \leq val[u] $$

2. 左偏性质

对于任意节点 $u$，其左子树的最短路径不小于右子树：

$$ dist[lc[u]] \geq dist[rc[u]] $$

由此可得递推公式：

$$ dist[u] = dist[rc[u]] + 1 $$

这一性质保证了树的"右偏最小"，从而确保合并操作的效率。

关键操作实现

合并（Merge）

合并是左偏树的核心操作。给定两棵左偏树根节点 $a$ 和 $b$：

1. 若任一节点为空，返回另一节点。
2. 确保 $val[a] \leq val[b]$，否则交换 $a$ 与 $b$。
3. 将 $b$ 与 $a$ 的右子树递归合并。
4. 合并后若左子树的 $dist$ 小于右子树，则交换左右子树以维持左偏性。
5. 更新 $dist[a] = dist[rc[a]] + 1$。

int merge(int a, int b) {
    if (!a || !b) return a | b;
    if (val[b] < val[a]) swap(a, b);
    rc[a] = merge(rc[a], b);
    if (dist[lc[a]] < dist[rc[a]]) 
        swap(lc[a], rc[a]);
    dist[a] = dist[rc[a]] + 1;
    return a;
}

通过始终向右子树合并，并在破坏左偏性时调整，保证了结构平衡。

取最小值

最小值位于当前树的根节点。结合并查集进行路径压缩，使得后续查询能快速定位所在堆的根。

int findRoot(int x) {
    return par[x] == x ? x : par[x] = findRoot(par[x]);
}

删除根节点

删除根节点时，需将其左右子树重新合并为新堆，并更新父指针关系：

void deleteRoot(int &root) {
    int l = lc[root], r = rc[root];
    lc[root] = rc[root] = 0;
    dist[root] = 0;
    root = merge(l, r);
    par[l] = par[r] = root;
}

插入新节点

插入等价于将单节点堆与原堆合并：

root = merge(root, newNode);

懒标记下传（如整体加减）

支持不影响相对大小的操作（如整体加常数），可通过延迟标记实现。在每次访问子节点前下传标记：

void pushDown(int u) {
    if (tag[u]) {
        val[u] += tag[u];
        if (lc[u]) tag[lc[u]] += tag[u];
        if (rc[u]) tag[rc[u]] += tag[u];
        tag[u] = 0;
    }
}

注意：需在 merge、delete 等操作中调用 pushDown。

应用实例：猴子王国（Monkey King）

题目描述：
初始有 $n$ 只猴子，每只独立成堆，权值为 $v_i$。进行 $m$ 次操作，每次指定两只猴子 $x,y$，将其所在堆的堆顶元素权值减半（向下取整），然后合并两个堆。输出每次合并后的堆顶值。

思路分析：
- 使用左偏树维护每个猴群的优先级。 - 每次操作先找到 $x,y$ 所在堆的根。 - 修改根的权值为原值的一半（注意负数处理）。 - 分别删除旧根，将剩余部分重新合并，并把原根作为新节点插入。 - 最后合并两个堆并输出新堆顶。

技巧说明：
由于 C++ 整除对负数向下取整，而题目要求正数下取整，故对奇数需特殊处理。例如，将 $a$ 减半应写作：

val = -(abs(val) >> 1); // 正确处理符号

参考实现

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e5 + 5;
int n, m;

struct LeftistTree {
    int lc[MAXN], rc[MAXN], dist[MAXN], par[MAXN];
    struct Node {
        int id, val;
        bool operator < (const Node &b) const {
            return val != b.val ? val < b.val : id < b.id;
        }
    } node[MAXN];

    int find(int x) {
        return par[x] == x ? x : par[x] = find(par[x]);
    }

    int merge(int a, int b) {
        if (!a || !b) return a | b;
        if (node[b] < node[a]) swap(a, b);
        rc[a] = merge(rc[a], b);
        if (dist[lc[a]] < dist[rc[a]])
            swap(lc[a], rc[a]);
        dist[a] = dist[rc[a]] + 1;
        return a;
    }

    void updateHalf(int u) {
        node[u].val = -(abs(node[u].val) >> 1);
    }

    void delRoot(int &root) {
        int l = lc[root], r = rc[root];
        lc[root] = rc[root] = 0;
        dist[root] = 0;
        root = merge(l, r);
        if (root) par[root] = root;
    }
} T;

int main() {
    while (~scanf("%d", &n)) {
        for (int i = 1; i <= n; ++i) {
            T.node[i].id = i;
            T.node[i].val = -read(); // 转换为小根堆
            T.par[i] = i;
            T.lc[i] = T.rc[i] = 0;
            T.dist[i] = 1;
        }
        T.dist[0] = -1;

        m = read();
        while (m--) {
            int x = read(), y = read();
            int rx = T.find(x), ry = T.find(y);
            if (rx == ry) {
                puts("-1"); continue;
            }

            T.updateHalf(rx); T.updateHalf(ry);

            T.delRoot(rx); T.delRoot(ry);

            rx = T.merge(rx, T.par[rx]); // 重建堆
            ry = T.merge(ry, T.par[ry]);

            int newRoot = T.merge(rx, ry);
            T.par[newRoot] = newRoot;

            printf("%d\n", -T.node[newRoot].val);
        }
    }
    return 0;
}