本文章由 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;
}
鲁ICP备2025150228号