一，理论

高效合并优先队列

外节点：只有一个儿子或没有儿子的节点，即左右儿子至少有一个为空节点的节点
距离：一个节点到离它最近的外节点的距离，即两节点之间路径的权值和。特别地，外节点的距离为0，空节点的距离为?1
左偏树：一种满足左偏性质的堆有序二叉树（左偏树的左偏性质体现在左儿子的距离大于右儿子的距离）
左偏树的距离：我们将一棵左偏树根节点的距离作为该树的距离

满足堆的基本性质

对于任意节点，左儿子的距离大于右儿子的距离
对于任意节点，其距离等于它的右儿子的距离加一
对于一棵n个节点的左偏树，其根节点的距离不超过 $l o g N$
对于一棵距离为d的左偏树，其节点数不少于 $2 k + 1 ? 1$

二，实现

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010;

int n;
int v[N], dist[N], l[N], r[N], idx;
int p[N];

bool cmp(int x, int y)
{
    if (v[x] != v[y]) return v[x] < v[y];
    return x < y;
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int merge(int x, int y)
{
    if (!x || !y) return x + y;
    if (cmp(y, x)) swap(x, y);
    r[x] = merge(r[x], y);
    if (dist[r[x]] > dist[l[x]]) swap(l[x], r[x]);
    dist[x] = dist[r[x]] + 1;
    return x;
}

int main()
{
    scanf("%d", &n);
    v[0] = 2e9;
    while (n -- )
    {
        int t, x, y;
        scanf("%d%d", &t, &x);
        if (t == 1)
        {
            v[ ++ idx] = x;
            dist[idx] = 1;
            p[idx] = idx;
        }
        else if (t == 2)
        {
            scanf("%d", &y);
            x = find(x), y = find(y);
            if (x != y)
            {
                if (cmp(y, x)) swap(x, y);
                p[y] = x;
                merge(x, y);
            }
        }
        else if (t == 3)
        {
            printf("%d\n", v[find(x)]);
        }
        else
        {
            x = find(x);
            if (cmp(r[x], l[x])) swap(l[x], r[x]);
            p[x] = l[x], p[l[x]] = l[x];
            merge(l[x], r[x]);
        }
    }

    return 0;
}