前置知识：二叉堆
首先，我们定义 外节点 为左儿子或右儿子为空的节点，定义外节点的 dist 为0，空节点的 dist 为-1 ，其他节点的dist为其到子树中最近的外节点的距离加一。
那么，左偏树是什么？左偏树是一棵二叉树，它不仅具有堆的性质，并且是「左偏」的：每个节点左儿子的 dist 都大于等于右儿子的 dist ，另外，每个节点的dist为其右儿子dist+1。
左偏树是一种可并堆，合并的过程参考下面的代码：
#define ls s[x].son[0] #define rs s[x].son[1] struct node{ int dis,val,son[2],rt; }s[150010]; int merge(int x,int y){//这里是小根堆的合并 if(!x||!y)return x+y;//一个堆为空则返回另一个堆 if(s[x].val>s[y].val||(s[x].val==s[y].val&&x>y))swap(x,y);//因为是小根堆，所以要值小的在前面 rs=merge(rs,y);//把x，y中小的那个作为根 让根的右儿子与另一个递归合并 因为要满足二叉堆的性质 if(s[ls].dis<s[rs].dis)swap(ls,rs);//因为要满足左儿子的dist大于右儿子的dist的性质 s[ls].rt=s[rs].rt=s[x].rt=x;//把左右儿子和根本身的父亲都设为根本身 s[x].dis=s[rs].dis+1;//根据dist的定义 根的dist为右儿子的dist+1； return x;//返回新根 }
另外 找一个堆的堆顶可以用并查集的路径压缩优化，即：
int get(int x){//并查集的路径压缩 if(s[x].rt==x)return x; s[x].rt=get(s[x].rt); return s[x].rt; }
假如要删掉一个点：
void pop(int x){ s[x].val=-1;//删点就是把自己的权值设为-1 s[ls].rt=ls; s[rs].rt=rs;//左右儿子的父亲设为左右儿子本身 s[x].rt=merge(ls,rs);//记得将原来的删的点的左右儿子合并 删的点的父亲指向新根（因为你只是删了一个点 不会使那个堆一分为二） }
所以这道题的代码就出来了：
#include<bits/stdc++.h> #define ls s[x].son[0] #define rs s[x].son[1] using namespace std; int n,t,a,b,c; struct node{ int dis,val,son[2],rt; }s[150010]; int merge(int x,int y){ if(!x||!y)return x+y; if(s[x].val>s[y].val||(s[x].val==s[y].val&&x>y))swap(x,y); rs=merge(rs,y); if(s[ls].dis<s[rs].dis)swap(ls,rs); s[ls].rt=s[rs].rt=s[x].rt=x; s[x].dis=s[rs].dis+1; return x; } int get(int x){ if(s[x].rt==x)return x; s[x].rt=get(s[x].rt); return s[x].rt; } void pop(int x){ s[x].val=-1; s[ls].rt=ls; s[rs].rt=rs; s[x].rt=merge(ls,rs); } int main(){ cin>>n>>t; s[0].dis=-1; for(int i=1;i<=n;i++){ s[i].rt=i; scanf("%d",&s[i].val); } for(int i=1;i<=t;i++){ scanf("%d%d",&a,&b); if(a==1){ scanf("%d",&c); if(s[b].val==-1||s[c].val==-1)continue; int B=get(b),C=get(c); if(B!=C){ s[B].rt=s[C].rt=merge(B,C); } }else{ if(s[b].val==-1)printf("-1 "); else printf("%d ",s[get(b)].val),pop(get(b)); } } return 0; }
推荐几个题？
洛谷 1456 monkey king
洛谷 2713 罗马游戏
另外 听说可并堆有stl， 在#