luoguP3377 【模板】左偏树（可并堆）

传送门

分析

可合并的二叉堆和之前的模板差不多，根据题意稍有个别改变； 详见代码； 代码

#include<bits/stdc++.h> #define N 100005 using namespace std; int n,x,y,k,h,m,cnt,fa[N],a[N],v[N],l[N],r[N],d[N]; int find(int x){ while(fa[x])x=fa[x]; return x; } int merge(int x,int y){ if(!x || !y)return x+y; if(a[x]>a[y]||(a[x]==a[y]&&x>y))swap(x,y); r[x]=merge(r[x],y); fa[r[x]]=x; if(d[r[x]]>d[l[x]])swap(l[x],r[x]); d[x]=d[r[x]]+1; return x; } int main(){ scanf("%d%d",&n,&m);d[0]=-1; for(int i=1;i<=n;i++)scanf("%d",&a[i]); for(int i=1;i<=m;i++){ scanf("%d",&k); if(k==1){ scanf("%d%d",&x,&y); if(a[x]==-1||a[y]==-1)continue; if(x==y)continue; int fx=find(x),fy=find(y); h=merge(fx,fy); }else{ scanf("%d",&x); if(a[x]==-1)printf("-1\n"); else{ y=find(x); printf("%d\n",a[y]); a[y]=-1; fa[l[y]]=fa[r[y]]=0; h=merge(l[y],r[y]); } } } return 0; }