/*
Mail to : miyubai@gamil.com
My Blog : www.baiyun.me
Link : http://www.cnblogs.com/MiYu || http://www.cppblog.com/MiYu
Author By : MiYu
Test : 1
Complier : g++ mingw32-3.4.2
Program : HDU_1512
Doc Name : Monkey King
题目意思:
有N只猴子, 每只都有一个力量值. 开始的时候互不认识, 它们之间会发生M次斗争. 每次发生a, b的斗争时, a, b都会从各自的朋友圈里拉出一个最强的, 之后两只猴子打, 打完后这两只猴子的力量值各减半. 并且打完后, 两只猴子的朋友圈的所有人都互相认识(也就是不会再打).
你的任务就是对于每个斗争, 若a, b是朋友, 那么输出-1, 否则输出打完后它们的朋友圈的最强猴子的力量值.
使用 普通 优先队列的话 估计会超时, 因为数据量很大 100000 ! !, 等下有空试试看.
对于每一个节点, 定义dis 表示X节点到最右边的空节点的距离的最小值
对于每个节点X, 要求X的左儿子的dis >= 右儿子的dis, 那么容易发现, 对于N个节点的左偏树, 其右儿子最多只有logN个节点.
合并操作就是让复杂度落在右儿子上, 从而达到logN的合并复杂度.
首先对于两个堆, 若其中一个为空, 返回另一个.
否则(这里以大根堆为例), a指向堆顶较大的堆, b指向另一个. 让a的右儿子和b合并, 合并后的子树作为a的右儿子.
接下来, 检查a的两个儿子是否满足dis, 不满足就交换两个儿子.
最后, 更新a的dis.
这样就容易实现堆的其他操作 ( 比如插入, 删除顶等 ).
另外 还需要用到 并查集.
*/
//#pragma warning( disable:4789 )
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <queue>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
using namespace std;
const int MM = 100010;
struct left {
int l,r,dis,val,dad;
} heap[MM];
int N, M;
inline int max ( const int &a, const int &b) {
return a > b ? a : b;
}
inline int find ( int &x ) {
return heap[x].dad == x ? x : heap[x].dad = find ( heap[x].dad );
}
inline void swap(int &a, int &b) {
a ^= b ^= a ^= b;
}
inline int merge ( int x, int y ) {
if ( x == 0 ) return y;
if ( y == 0 ) return x;
if ( heap[y].val > heap[x].val ) swap ( x, y );
heap[x].r = merge ( heap[x].r, y );
heap[heap[x].r].dad = x;
if ( heap[ heap[x].l ].dis < heap[ heap[x].r ].dis )
swap ( heap[x].l, heap[x].r );
if ( heap[x].r == 0 ) heap[x].dis = 0;
else heap[x].dis = heap[ heap[x].r ].dis + 1;
return x;
}
inline int push ( int x, int y ) {
return merge ( x, y );
}
inline int pop ( int &x ) {
int l = heap[x].l;
int r = heap[x].r;
heap[l].dad = l;
heap[r].dad = r;
heap[x].l = heap[x].r = heap[x].dis = 0;
return merge ( l, r );
}
inline bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<'0'||in>'9')) in=getchar();
if(in=='-'){ IsN=true;num=0;}
else num=in-'0';
while(in=getchar(),in>='0'&&in<='9'){
num*=10,num+=in-'0';
}
if(IsN) num=-num;
return true;
}
int main() {
while ( scan_d ( N ) ) {
for ( int i = 1; i <= N; ++ i ) {
scan_d ( heap[i].val );
heap[i].l = heap[i].r = heap[i].dis = 0;
heap[i].dad = i;
}
scan_d ( M );
int a, b, x, y;
while ( M -- ) {
scan_d (a); scan_d (b);
x = find ( a );
y = find ( b );
if ( x == y ) {
puts ( "-1" );
} else {
heap[x].val /= 2;
int xx = push ( pop ( x ), x );
heap[y].val /= 2;
int yy = push ( pop ( y ), y );
printf ( "%d\n", heap[ merge ( xx, yy ) ].val );
}
}
}
return 0;
}