思路：

左偏树里面掺了一些并查集的应用

这里放一份左偏树的代码模板

重点就是merge函数了……

int merge(int k1,int k2){

    if(!k1||!k2)return k1+k2;

    if(tr[k1].w<tr[k2].w)swap(k1,k2);

    tr[k1].r=merge(tr[k1].r,k2);

    if(tr[tr[k1].l].dis<tr[tr[k1].r].dis)swap(tr[k1].l,tr[k1].r);

    tr[k1].dis=tr[tr[k1].r].dis+1;

    return k1;

}

插入：合并原树和新节点。

删除最小值：合并左右子树。

删在某个地方的值：打个标记 以后用的时候再忽略

在这道题中 删的时候 找到左右子树 并查集变成它自己 再合并

//By SiriusRen

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

#define N 100050

int n,m,root[N],xx,yy,f[N];

struct Tree{int l,r,w,dis;void init(){l=r=dis=0;}}tr[N];

int find(int x){return x==f[x]?x:f[x]=find(f[x]);}

int merge(int k1,int k2){

    if(!k1||!k2)return k1+k2;

    if(tr[k1].w<tr[k2].w)swap(k1,k2);

    tr[k1].r=merge(tr[k1].r,k2);

    f[tr[k1].r]=k1;

    if(tr[tr[k1].l].dis<tr[tr[k1].r].dis)swap(tr[k1].l,tr[k1].r);

    tr[k1].dis=tr[tr[k1].r].dis+1;

    return k1;

}

int pop(int x){

    tr[x].w/=2;

    int l=tr[x].l,r=tr[x].r;

    f[l]=l,f[r]=r;

    tr[x].init();

    int t=merge(l,r);

    return merge(x,t);

}

int main(){

    while(~scanf("%d",&n)){

        for(int i=1;i<=n;i++){

            scanf("%d",&tr[i].w);

            tr[i].init(),f[i]=i;

        }

        scanf("%d",&m);

        for(int i=1;i<=m;i++){

            scanf("%d%d",&xx,&yy);

            int fx=find(xx),fy=find(yy);

            if(fx==fy)puts("-1");

            else{

                int tx=pop(fx),ty=pop(fy);

                printf("%d\n",tr[merge(tx,ty)].w);

            }

        }

    }

}