题目大意：有n个猴子。每个猴子有一个力量值，力量值越大表示这个猴子打架越厉害。如果2个猴子不认识，他们就会找他们认识的猴子中力量最大的出来单挑，单挑不论输赢，单挑的2个猴子力量值减半，这2拨猴子就都认识了，不打不相识嘛。现在给m组询问，如果2只猴子相互认识，输出-1，否则他们各自找自己认识的最牛叉的猴子单挑，求挑完后这拨猴子力量最大值。
左偏大根加并查
代码都懒的贴了...
#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 maxn = ;
struct node {
int l,r,dis,val,par;
} heap[maxn];
int N, M;
int find ( int &x ) {
return heap[x].par == x ? x : heap[x].par = find ( heap[x].par );
}
int merge(int rt1,int rt2)
{
if (rt1==) return rt2;
if (rt2==) return rt1;
if ( heap[rt2].val>heap[rt1].val )swap(rt1,rt2);
heap[rt1].r = merge(heap[rt1].r,rt2);
heap[heap[rt1].r].par = rt1;
if ( heap[ heap[rt1].l ].dis < heap[ heap[rt2].r ].dis )
swap ( heap[rt1].l, heap[rt1].r );
else heap[rt1].dis = heap[ heap[rt1].r ].dis + ;
return rt1;
}
int push ( int x, int y ) {
return merge ( x, y );
}
int pop ( int &x ) {
int l = heap[x].l;
int r = heap[x].r;
heap[l].par = l;
heap[r].par = r;
heap[x].l = heap[x].r = heap[x].dis = ;
return merge ( l, r );
}
bool scan_d(int &num) {
char in;bool IsN=false;
in=getchar();
if(in==EOF) return false;
while(in!='-'&&(in<''||in>'')) in=getchar();
if(in=='-'){ IsN=true;num=;}
else num=in-'';
while(in=getchar(),in>=''&&in<=''){
num*=,num+=in-'';
}
if(IsN) num=-num;
return true;
}
int main() {
while ( scan_d ( N ) ) {
for ( int i = ; i <= N; ++ i ) {
scan_d ( heap[i].val );
heap[i].l = heap[i].r = heap[i].dis = ;
heap[i].par = 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 /= ;
int px = push ( pop ( x ), x );
heap[y].val /= ;
int py = push ( pop ( y ), y ); printf ( "%d\n", heap[ merge ( px, py ) ].val );
}
}
}
return ;
}