/*
Mail to : miyubai@gamil.com
My Blog : www.baiyun.me
Link : http://www.cnblogs.com/MiYu || http://m.shnenglu.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;
}