左偏树
维护对的性质，同时维护dis值保证合并复杂度
合并时类似于可持久化treap
#include<cstdio> #include<algorithm> inline int read() { int x=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar(); return x; } const int maxn = 100010; struct node { int fa,dis,key,ch[2]; node() { key=fa=dis=0; } }tree[maxn]; inline int ls(int x) {return tree[x].ch[0];} inline int rs(int x) {return tree[x].ch[1];} int n,m; int find(int x) { if(tree[x].fa) return find(tree[x].fa); else return x; } inline void update(int x) { tree[x].dis=tree[tree[x].ch[1]].dis+1; } int merge(int x,int y) { if(!x||!y)return x+y; if(tree[x].key>tree[y].key||(tree[x].key==tree[y].key&&x>y))std::swap(x,y); tree[x].ch[1]=merge(tree[x].ch[1],y); tree[tree[x].ch[1]].fa=x; if(tree[tree[x].ch[1]].dis>tree[tree[x].ch[0]].dis)std::swap(tree[x].ch[0],tree[x].ch[1]); update(x); return x; } void delet(int x) { int now=tree[x].fa;int top=merge(tree[x].ch[1],tree[x].ch[0]); tree[top].fa=now;tree[x].key=-1; while(now) { if(tree[tree[now].ch[0]].dis<tree[tree[now].ch[1]].dis)std::swap(tree[now].ch[0],tree[now].ch[1]); if(tree[now].dis==tree[tree[now].ch[1]].dis+1)return; tree[now].dis=tree[tree[now].ch[1]].dis+1; now=tree[now].fa; } } int main() { n=read(),m=read(); for(int i=1;i<=n;++i) tree[i].key=read(); while(m--) { int op=read(); if(op==1) { int x=read(),y=read(); if(tree[x].key==-1||tree[y].key==-1||x==y)continue; merge(find(x),find(y)); } else { int x=read(); if(tree[x].key==-1)puts("-1"); else x=find(x), printf("%d ",tree[x].key), delet(x); } } return 0; }
斐波那契堆