本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-02-28 23:06:33

upd: 在题解区翻到了和我一样的做法。

本想练习左偏树，但看到这道题之后自己乱口胡了一个非正解的做法。
写了写，结果没想到直接 A 了。。。。。

题解

考虑使用 $n$ 个小根堆，排序方式为按大小为第一关键字，输入顺序为第二关键字，升序排列。

至于记录每个数字在哪个堆，用并查集维护。

合并的时候暴力合并，每次把小的堆加入大的堆。

删除的时候直接将要删的数弹出，然后标记上已删除。

结束。

关于时间复杂度：
自我感觉是 $O(n \log^2 n)$ 的。

实际运行时间与正解没多少区别。

Code

#include <bits\/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
int fa[maxn];
bool del[maxn];
priority_queue<pair<int,int> ,vector<pair<int,int> >,greater<pair<int,int> > > q[maxn];
int find(int x)
{
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
    if(del[x]||del[y])return;
    int idx=find(x);
    int idy=find(y);
    if(idx==idy)return;
    if(q[idx].size()>q[idy].size())
    {
        while(!q[idy].empty())
        {
            q[idx].push(q[idy].top());
            q[idy].pop();
        }
        fa[idy]=idx;
    }
    else
    {
        while(!q[idx].empty())
        {
            q[idy].push(q[idx].top());
            q[idx].pop();
        }
        fa[idx]=idy;
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int ai;
        scanf("%d",&ai);
        q[i].push(make_pair(ai,i));
        fa[i]=i;
    }
    int op,x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d",&x,&y);
            merge(x,y);
        }
        else
        {
            scanf("%d",&x);
            if(del[x])
            {
                printf("-1\n");
                continue;
            }
            int idx=find(x);
            printf("%d\n",q[idx].top().first);
            del[q[idx].top().second]=1;
            q[idx].pop();
            
        }
    }
    return 0;
}