Monkey King

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2543    Accepted Submission(s): 1064

5
20
16
10
10
4
5
2 3
3 4
3 5
4 5
1 5

8
5
5
-1
10

题目大意：有n个猴子，一开始每个猴子只认识自己。每个猴子有一个力量值，力量值越大表示这个猴子打架越厉害。如果2个猴子不认识，他们就会找他们认识的猴子中力量最大的出来单挑，单挑不论输赢，单挑的2个猴子力量值减半，这2拨猴子就都认识了，不打不相识嘛。现在给m组询问，如果2只猴子相互认识，输出-1，否则他们各自找自己认识的最牛叉的猴子单挑，求挑完后这拨猴子力量最大值。

题目分析：首先很明显这题涉及到集合并的操作，要用到并查集。其次要找到某一拨猴子中力量最大值，找最大值最快的应该是堆。2拨猴子要快速合并而又不失堆的特性，想来想去左偏树比较合适。

关于左偏树，百度写的很详细。大致说两句。

首先左偏树是一个堆，具体什么堆看题目要求，比如这题就要求一个大堆。

其次左偏树顾名思义还有左偏的性质。这里的左偏不是说树的左子树就一定比右子树大。左偏树每个节点除了堆的关键字key外，还有一个关键字dis，距离，这是左偏树的特色。左偏树定义这样一类节点：如果一个节点的左右子树有空树，称之为外点，树根到一个外点的最近距离为dis。比如一颗叶子节点的dis为0。左偏树就是根据dis值来调整姿势的。左偏树保证左偏的性质：节点的左子树的dis值要不小于右子树的dis值。也就是说左偏树从根节点一路向右能最快访问到外点。

所以左偏树其实就是一颗有左偏性质的堆有序二叉树。

左偏树并不是一颗平衡树。因为左偏树的主要功能是快速访问最值节点以及修改后的快速恢复。所以左偏树放弃了平衡 的性质。相反，一颗平衡的左偏树反而会影响左偏树的性能。

左偏树详细内容可以看这篇左偏树的特点及其应用，讲的十分详细。

关于这题，用一个并查集维护猴子的集合，左偏树用来快速合并，并且快速保持大堆性质。并查集的并操作其实可以在左偏树合并的时候进行。

详情请见代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100005;
int m,n;
int set[N];
struct node
{
    int l,r,dis,key;
}tree[N];

int find(int a)
{
    int root = a;
    while(root != set[root])
        root = set[root];
    int parent = set[a];
    while(parent != root)//路径压缩
    {
        set[a] = root;
        a = parent;
        parent = set[a];
    }
    return root;
}

int merge(int a,int b)
{
    if(!a)
        return b;
    if(!b)
        return a;
    if(tree[a].key < tree[b].key)//大堆
        swap(a,b);
    tree[a].r = merge(tree[a].r,b);
    set[tree[a].r] = a;//并查
    if(tree[tree[a].l].dis < tree[tree[a].r].dis)
        swap(tree[a].l,tree[a].r);
    if(tree[a].r)
        tree[a].dis = tree[tree[a].r].dis + 1;
    else
        tree[a].dis = 0;
    return a;
}

int pop(int a)
{
    int l = tree[a].l;
    int r = tree[a].r;
    set[l] = l;//因为要暂时删掉根，所以左右子树先作为根
    set[r] = r;
    tree[a].l = tree[a].r = tree[a].dis = 0;
    return merge(l,r);
}

int nextint()
{
    char c;
    int ret = 0;
    while((c = getchar()) > '9' || c < '0')
        ;
    ret = c - '0';
    while((c = getchar()) >= '0' && c <= '9')
        ret = ret * 10 + c - '0';
    return ret;
}

void print(int a)
{
    if(!a)
        return;
    print(a/10);
    putchar(a%10 + '0');
}

int main()
{
    int a,b,i;
    while(~scanf("%d",&n))
    {
        for(i = 1;i <= n;i ++)
        {
            //scanf("%d",&tree[i].key);
            tree[i].key = nextint();
            set[i] = i;
            tree[i].l = tree[i].r = tree[i].dis = 0;
        }
       // scanf("%d",&m);
        m = nextint();
        while(m --)
        {
            //scanf("%d%d",&a,&b);
            a = nextint();
            b = nextint();
            int ra = find(a);
            int rb = find(b);
            //printf("%d  %d\n",ra,rb);
            if(ra == rb)
                printf("-1\n");
            else
            {
                int rra = pop(ra);//ra左右子树合并
                tree[ra].key /= 2;
                ra = merge(rra,ra);//重新插入ra 找到合适的位置
                int rrb = pop(rb);
                tree[rb].key /= 2;
                rb = merge(rrb,rb);
                print(tree[merge(ra,rb)].key);
                putchar(10);
                //printf("%d\n",tree[merge(ra,rb)].key);
            }
        }
    }
    return 0;
}
//703MS	2244K  无优化
//250MS	2184K  输入优化
//203MS	2184K  输入输出优化