正題

題目鏈接:https://www.luogu.com.cn/problem/P3377

---

題目大意

開始時(shí)$n$個(gè)只有一個(gè)數(shù)的集合，要求支持

合并兩個(gè)集合

查詢一個(gè)集合中的最小值并刪除

---

解題思路

左偏樹就是維護(hù)一個(gè)滿足以下性質(zhì)的樹

對于$va{l}_x$有$va{l}_x<va{l}_{l{s}_x}$且$va{l}_x<va{l}_{r{s}_x}$

對于任何節(jié)點(diǎn)有左子樹的深度大于右子樹的深度

每次合并時(shí)我們只需要將$val$小的合并到$val$大的右子樹上，然后每次合并完之后就判斷左右兩邊的深度大小。

時(shí)間復(fù)雜度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=1e5+10; int n,m,val[N]; struct Left_tree{int dis[N],fa[N],t[N][2];int Merge(int x,int y){if(!x||!y) return x+y;if(val[x]>val[y]||(val[x]==val[y]&&x>y))swap(x,y);int &ls=t[x][0],&rs=t[x][1];rs=Merge(rs,y);if(dis[ls]<dis[rs]) swap(ls,rs);fa[rs]=fa[ls]=x;dis[x]=dis[rs]+1;return x;}void Del(int x){int ls=t[x][0],rs=t[x][1];fa[ls]=ls;fa[rs]=rs;val[x]=-1;fa[x]=Merge(ls,rs);}int Get(int x){return (fa[x]==x)?(x):(fa[x]=Get(fa[x]));} }T; int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%d",&val[i]),T.fa[i]=i;while(m--){int op,x,y;scanf("%d%d",&op,&x);if(op==1){scanf("%d",&y);if(val[x]==-1||val[y]==-1)continue;x=T.Get(x);y=T.Get(y);T.Merge(x,y);}if(op==2){if(val[x]==-1){printf("-1\n");continue;}x=T.Get(x);printf("%d\n",val[x]);T.Del(x);}} }

總結(jié)

以上是生活随笔為你收集整理的P3377-[模板]左偏树(可并堆)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。