左偏树是可并堆的一种实现方法。
左偏，很容易形象地理解它是什么意思。
但对于一棵树，如何用形象和具体化的语言来描述左偏性质？
考虑定义 \(dis_i\) 表示 \(i\) 的子树中最近的空节点理 \(i\) 点的距离。
空节点是什么意思？由于左偏树是一棵二叉树，所以一个点没有左儿子/右儿子，其实可以看做其有一个左空儿子/右空儿子。
不难发现 \(dis_i\) 等价与 \(i\) 的子树往下拓展 \(1\sim dis_i-1\) 层都将是满二叉树，当拓展到 \(dis_i\) 层时其一定不是一棵满二叉树。
感性理解一下 \(dis_i\) 可以用来衡量一个点 \(i\) 的子树的茂密程度。
那么左偏的表示就呼之欲出了，\(dis_{ls}\ge dis_{rs}\)，即左边比右边更茂密。
那么维护 \(dis\) 也变得十分方便，即 \(dis_x=dis_{rs}+1\)。
好了，左偏树的左偏性质搞好了，堆性质维护起来也很容易，关键是，其作为可并堆，如何合并？
类似 FHQ 与线段树合并，设一个 \(merge(x,y)\) 表示将 \(x,y\) 合并后的新节点。
每次 \(merge(x,y)\)，我们将更小的点拿出来作为根（为了满足堆性质），然后将另外一个点与与更小的点的右儿子进行合并？
为什么是右儿子？因为我们再满足左偏条件下还要保证左右子树相对均匀。
那 \(merge\) 完了不再左偏了怎么办？交换一下左右子树即可。
这样合并就做完了。
删除一个点怎么做？
考虑直接合并该点的左右儿子即可。
那么就只差最后一步了，找某个点对应左偏树的根。
这看似轻松，实则不然，如果用朴素并查集，无法支持左偏树的删除操作，如果暴力跳的话，左偏树合并虽然是 \(O(\log n)\)，可树高确是实打实的 \(O(n)\)。
考虑在左偏树上进行路径压缩，然后类似并查集那样不断 find，这么做的话，即使将一个点删掉，那么由于之前有的节点的路径压缩时指向的它，所以这个节点依然会在路径压缩中以另一种形式存在。
做完了。
代码
ll n,m,a[1000005],ls[1000005],rs[100005],fa[1000005],dis[1000005],f[1000005];
bool del[1000005];
ll find(ll x){return x==f[x]?x:f[x]=find(f[x]);}
bool cmp(ll x,ll y){return a[x]==a[y]?x<y:a[x]<a[y];}
void maintain(ll x){
if(ls[x]) fa[ls[x]]=x;
if(rs[x]) fa[rs[x]]=x;
if(dis[ls[x]]<dis[rs[x]]) swap(ls[x],rs[x]);
dis[x]=dis[rs[x]]+1;
return;
}
ll merge(ll x,ll y){
if(!x||!y) return x+y;
if(cmp(y,x)) swap(x,y);
rs[x]=merge(rs[x],y);
maintain(x);
return x;
}
int main(){
rd(n);
rd(m);
rep(i,1,n){
dis[i]=1;
f[i]=i;
rd(a[i]);
}
while(m--){
ll opt;
rd(opt);
if(opt==1){
ll x,y;
rd(x);
rd(y);
if(del[x]||del[y]) continue;
ll fx=find(x),fy=find(y);
if(fx==fy) continue;
f[fx]=f[fy]=merge(fx,fy);
}
else{
ll x;
rd(x);
if(del[x]){
puts("-1");
continue;
}
ll fx=find(x);
printf("%lld\n",a[fx]);
del[fx]=1;
dis[fx]=-1;
fa[ls[fx]]=fa[rs[fx]]=0;
f[fx]=f[ls[fx]]=f[rs[fx]]=merge(ls[fx],rs[fx]);
}
}
}