首页 > 代码库 > 左偏树
左偏树
真不好意思把luogu的链接放出来,数据也太水了把,想吐。。
简单叙述一下题意把,不粘贴了,没有脸。
刚开始给定若干个堆,然后你可以吧两个堆合并,或者删除值为x并输出x所在的堆min
%:pragma GCC optimize("O3")#include<bits/stdc++.h>#define maxn 200000using namespace std;struct TREE{int val,dis,l,r;}tr[maxn];int x,y,t1,n,m,fa[maxn];template<typename tp>void read(tp & dig){ char c=getchar();dig=0; while(!isdigit(c))c=getchar(); while(isdigit(c))dig=dig*10+c-‘0‘,c=getchar();}inline int find(int x){while(fa[x]) x=fa[x];return x;}//这里不是并查集,而是找他的父节点 inline int merge(int a,int b){ if(!a) return b;if(!b) return a; if(tr[a].val>tr[b].val||(tr[a].val==tr[b].val&&a>b)) swap(a,b);//维护一个小根堆 tr[a].r=merge(tr[a].r,b); fa[tr[a].r]=a; if(tr[tr[a].l].dis<tr[tr[a].r].dis) swap(tr[a].l,tr[a].r); if(tr[a].r==0) tr[a].dis=0; else tr[a].dis=tr[tr[a].r].dis+1; return a;}int main(){ read(n),read(m);tr[0].val=-1;//这里要加上,luogu数据真心水 for(int i=1;i<=n;i++)read(tr[i].val); while(m--) { read(t1); if(t1==1) { read(x),read(y); if(tr[x].val==-1||tr[y].val==-1) continue; x=find(x),y=find(y); if(x!=y) merge(x,y); } if(t1==2) { read(x); if(tr[x].val==-1) puts("-1"); else { printf("%d\n",tr[x=find(x)].val); fa[tr[x].l]=fa[tr[x].r]=0; merge(tr[x].l,tr[x].r); tr[x].val=-1; } } } return 0;}
左偏树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。