hdu1512

题解：

每一次合并两个对

修改操作就和普通的堆一样

代码：

#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200005;
int val[N],n,m,rt[N],tot,dist[N],c[N][2],a[N],x,y,fa[N],size[N];
int merge(int x,int y)
{
    if (!x||!y)return x+y;
    if (val[x]<val[y])swap(x,y);
    c[x][1]=merge(c[x][1],y);
    size[x]=size[c[x][0]]+size[c[x][1]]+1;
    fa[c[x][1]]=x;
    if (dist[c[x][0]]<dist[c[x][1]])swap(c[x][0],c[x][1]);
    dist[x]=dist[c[x][1]]+1;
    return x;
}
int top(int x)
{
     for (;fa[x]!=x;x=fa[x]);
     return x;
}
int newnode(int x)
{
    val[++tot]=x;
    size[tot]=1;fa[tot]=tot;
    c[tot][0]=c[tot][1]=dist[tot]=0;
    return tot;
}
void down(int x)
{
    int i=x;
    if (c[x][0]&&val[i]<val[c[x][0]])i=c[x][0];
    if (c[x][1]&&val[i]<val[c[x][1]])i=c[x][1];
    if (x!=i)
     {
         swap(val[x],val[i]);
         down(i);
     }
}
int main()
{
    while (~scanf("%d",&n))
     {
         memset(val,0,sizeof val);
         memset(c,0,sizeof c);
         memset(rt,0,sizeof rt);
         memset(fa,0,sizeof fa);
         tot=0;
         for (int i=1;i<=n;i++)scanf("%d",&a[i]);
         for (int i=1;i<=n;i++)rt[i]=newnode(a[i]);
         scanf("%d",&m);
         while (m--)
          {
              scanf("%d%d",&x,&y);
              int tx=top(x),ty=top(y);
              if (tx==ty)puts("-1");
              else
               {
                   val[tx]/=2;down(tx);
                   val[ty]/=2;down(ty);
                   rt[tx]=merge(tx,ty);rt[ty]=0;
                   printf("%d
",val[rt[tx]]);
               }
          }
     }
}