[HDU1512/ZOJ2334]Monkey King-左偏树-可合并堆

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Problem Monkey King

Solution

本题是裸的左偏树，一个模板就可以过了。对于每个操作对节点先删除/2再合并。
注意本题在HDU上评测特别坑，是多组数据，而且经常出现MLE的情况。很可能是其中初始化的问题。
斜堆可以更快。具体请查询IOI2015黄源河集训队论文。

AC Code

#include "iostream"

#include "cstdio"

using namespace std;

struct LeftistTree{

    int dist,n,lc,rc,fa;

}a[];

int find(int x){

    while(a[x].fa!=x)x=a[x].fa;

    return x;

}

int n,m;

int x,y,ans,fx,fy,u,v,dx,dy;

int merge(int x,int y){

    if(x==)return y;

    if(y==)return x;

    if(a[x].n<a[y].n)swap(x,y);

    a[x].rc=merge(a[x].rc,y);

    a[a[x].rc].fa=x;

    if(a[a[x].lc].dist<a[a[x].rc].dist)swap(a[x].lc,a[x].rc);

    if(a[x].rc!=)a[x].dist=a[a[x].rc].dist+;

    else a[x].dist=;

    return x;

}

int delt(int x){

    int ret=merge(a[x].lc,a[x].rc);

    a[a[x].lc].fa=ret;

    a[a[x].rc].fa=ret;

    a[x].lc=a[x].rc=a[x].dist=;

    a[x].fa=x;

    return ret;

}

int main(){

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

        a[].lc=;a[].rc=;a[].fa=;

        for(int i=;i<=n;i++)scanf("%d",&a[i].n),a[i].fa=i,a[i].dist=,a[i].lc=,a[i].rc=;

        scanf("%d",&m);

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

            scanf("%d%d",&x,&y);

            fx=find(x),fy=find(y);

            if(fx==fy)printf("-1\n");else{

                dx=delt(fx),dy=delt(fy);

                a[fx].n/=;

                a[fy].n/=;

                dx=merge(dx,fx);

                dy=merge(dy,fy);

                ans=merge(dx,dy);

                printf("%d\n",a[ans].n);

            }

        }

    }

}