题目描述
如题，一开始有N个小根堆，每个堆包含且仅包含一个数。接下来需要支持两种操作：
操作1： 1 x y 将第x个数和第y个数所在的小根堆合并（若第x或第y个数已经被删除或第x和第y个数在用一个堆内，则无视此操作）
操作2： 2 x 输出第x个数所在的堆最小数，并将其删除（若第x个数已经被删除，则输出-1并无视删除操作）
输入输出格式
输入格式：
第一行包含两个正整数N、M，分别表示一开始小根堆的个数和接下来操作的个数。
第二行包含N个正整数，其中第i个正整数表示第i个小根堆初始时包含且仅包含的数。
接下来M行每行2个或3个正整数，表示一条操作，格式如下：
操作1 ： 1 x y
操作2 ： 2 x
输出格式：
输出包含若干行整数，分别依次对应每一个操作2所得的结果。
裸题吧，附上模板。
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std; const int NN=1e5+; int n,m,a[NN];
int r[NN],l[NN],d[NN],fa[NN];
bool died[NN]; int find(int num)
{
if (fa[num]!=num) return find(fa[num]);
return num;
}
int merge(int x,int y)
{
if (!x) return y;
if (!y) return x;
if (a[x]>a[y]) swap(x,y);
r[x]=merge(r[x],y);
fa[r[x]]=x;
if (d[r[x]]>d[l[x]]) swap(r[x],l[x]);
d[x]=d[r[x]]+;
return x;
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=n;i++)
{
fa[i]=i;
scanf("%d",&a[i]);
}
for (int i=;i<=m;i++)
{
int k,u,v;
scanf("%d",&k);
if (k==)
{
scanf("%d%d",&u,&v);
if (died[u]||died[v]) continue;
int x=find(u),y=find(v);
if (x!=y)
{
int t=merge(x,y);
fa[t]=t;
}
}
else
{
scanf("%d",&u);
int x=find(u);
if (died[x]) printf("-1\n");
else
{
printf("%d\n",a[x]);
died[x]=;
int t=merge(r[x],l[x]);
fa[t]=t;
}
}
}
}