sup-extra HDU-1512 Monkey King 左偏树

Posted at 2019-01-19 ICPC 

HDU-1512 Monkey King 左偏树

---

题意是每次有两只猴子要battle，但是猴子battle的时候会叫自己认识的攻击力最高的猴子，并且battle结束后参加battle的猴子攻击力减半。

可以看出来这题就是要你维护两个优先队列，每次battle时弹出攻击力最高的，然后将攻击力减半再重新合并成一个新的队列。为了支持合并操作选用左偏树来实现。唯一需要注意的问题就是要记得更新你询问的节点的左偏树的根节点。另外之前因为没有使用memset导致MLE，意义不明

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#define maxl 100003
using namespace std;
int n,m;
int root[maxl],lef[maxl],rig[maxl],val[maxl],dist[maxl];
int findroot(int k)//寻找目前的左偏树根节点的同时更新沿途的节点
{
    if(root[k]==k) return k;
    else return root[k]=findroot(root[k]);
}
int ltree_merge(int x,int y)//左偏树合并
{
    if(x==0||y==0) return x+y;
    if(val[x]<val[y]) swap(x,y);
    rig[x]=ltree_merge(rig[x],y);
    root[rig[x]]=x;
    if(dist[rig[x]]>dist[lef[x]])
        swap(rig[x],lef[x]);
    if(rig[x]==0)
        dist[x]=0;
    else dist[x]=dist[rig[x]]+1;
    return x;
}
int ltree_pop(int a,int b)//左偏树删除根节点
{
    int l1=lef[a],l2=lef[b],r1=rig[a],r2=rig[b];
    root[l1]=l1;root[l2]=l2;root[r1]=r1;root[r2]=r2;
    lef[a]=rig[a]=lef[b]=rig[b]=dist[a]=dist[b]=0;
    val[a]/=2;val[b]/=2;
    a=ltree_merge(a,b);
    b=ltree_merge(l1,r1);
    a=ltree_merge(a,b);
    b=ltree_merge(l2,r2);
    return ltree_merge(a,b);
}
int main(void)
{
    while(~scanf("%d",&n))
    {
        memset(root,0,sizeof(root));
        memset(lef,0,sizeof(lef));
        memset(rig,0,sizeof(rig));
        memset(dist,0,sizeof(dist));
        for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        root[i]=i;
    }

    scanf("%d",&m);
    while(m--)
    {
        int mid1,mid2;
        scanf("%d%d",&mid1,&mid2);
        findroot(mid1);
        findroot(mid2);
        if(root[mid1]==root[mid2])
            printf("-1\n");
        else
        {
            int res;
            res=ltree_pop(root[mid1],root[mid2]);
            printf("%d\n",val[res]);
        }
    }
    }
	return 0;
}