【HDU1512】Monkey King 左偏树+并查集

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1512

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

Problem Description

Once in a forest, there lived N aggressive monkeys. At the beginning, they each does things in its own way and none of them knows each other. But monkeys can't avoid quarrelling, and it only happens between two monkeys who does not know each other. And when it happens, both the two monkeys will invite the strongest friend of them, and duel. Of course, after the duel, the two monkeys and all of there friends knows each other, and the quarrel above will no longer happens between these monkeys even if they have ever conflicted.

Assume that every money has a strongness value, which will be reduced to only half of the original after a duel(that is, 10 will be reduced to 5 and 5 will be reduced to 2).

And we also assume that every monkey knows himself. That is, when he is the strongest one in all of his friends, he himself will go to duel.

Input

There are several test cases, and each case consists of two parts.

First part: The first line contains an integer N(N<=100,000), which indicates the number of monkeys. And then N lines follows. There is one number on each line, indicating the strongness value of ith monkey(<=32768).

Second part: The first line contains an integer M(M<=100,000), which indicates there are M conflicts happened. And then M lines follows, each line of which contains two integers x and y, indicating that there is a conflict between the Xth monkey and Yth.

Output

For each of the conflict, output -1 if the two monkeys know each other, otherwise output the strongness value of the strongest monkey in all friends of them after the duel.

Sample Input

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

Sample Output

8
5
5
-1
10
本来是裸裸的左偏树加并查集,然而我昨天却调了一晚上……
样例什么的都能过,就是交上去WA,今天早上洗把脸再看一遍题……
"There are several test cases, and each case consists of two parts."
哇啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊!!!多组数据啊!!!
然后1分钟AC……不看清题毁一生啊~
然后讲一讲左偏树是什么东西吧,左偏树其实实一个可并堆,虽然基本上所有操作都是logn的,但是写起来非常简单,而且平均起来常数很小,很好用。
这里先给出定义:左偏树是一棵二叉树,满足以下2个性质:
  1. 堆性质,即任意一个节点都比它的儿子节点大(或小);
  2. 左偏性,定义外界点为有子节点为空的节点,定义一个节点的距离为到最近的外节点的路径长度,则任意一个节点左子节点的距离不小于右子节点的距离。

易得,外界点距离为0,不妨设空节点距离为-1,那么我们很容易推得一个节点的距离为右子节点的距离+1,并且还能得出一个节点的距离不大于这颗子树的size的对数(log size)。

那么就来介绍两棵左偏树的合并:

不妨设这里的LTree(左偏树)为大根堆,a.key>=b.key,那么

merge(LTree a,LTree b)=merge(LTree a.r,LTree b)

简单地说就是将根节点key值较小的左偏树与另一颗左偏树的右子树合并,这是递归的,边界情况为有一个节点为空,就直接返回另一棵树。

这个过程中可能会出现右子树的距离大于左子树的情况,不要担心,直接交换左右子树即可。

这个操作的复杂度是两棵树根的距离之和,也就是log级别的

学会了合并那么插入和弹出堆顶就很简单了。

插入即对一个节点单独建立一棵左偏树,然后合并,

弹出堆顶就是将堆顶删除后合并左右子树。

都是log级别的复杂度

亮点是非常好写(比配对堆,斐波拉契堆好写也好想多了),思路也非常清晰(话说有pb_ds为啥还要手写可并堆啊???)

然后贴代码(我写了内存回收,然后写了两个struct……习惯)

 

不如来评论一发?