hdu 1512 Monkey King （左偏树 实现 可并堆）

模板：http://hi.baidu.com/cjn1466572108/item/c2b7c13e58f7aba1b711dba6

待验证

//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FD(i, b, a) for(int i = (b); i >= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(a, v) memset(a, v, sizeof(a))
#define PB push_back
#define MP make_pairtypedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 310000;struct Node{int l, r;int fa;int v, dis;bool operator<(const Node &rhs) const{return v < rhs.v;///大顶堆}
}N[maxn];int root[maxn];
int findset(int x)
{return x == N[x].fa ? x : N[x].fa = findset(N[x].fa);
}void Newnode(int i, int val)
{N[i].l = N[i].r = 0;N[i].fa = i;N[i].dis = 0;N[i].v = val;
}void Init(int n)
{N[0].l = N[0].r = 0;N[0].v = 0; N[0].dis = -1;N[0].fa = 0;int val;for (int i = 1; i <= n; i++){scanf("%d", &val);Newnode(i, val);}
}int Merge(int A, int B)
{if (A == 0) return B;if (B == 0) return A;if (N[A] < N[B]) swap(A, B);N[A].r = Merge(N[A].r, B);N[N[A].r].fa = A;///if (N[N[A].l].dis < N[N[A].r].dis) swap(N[A].l, N[A].r);N[A].dis = N[N[A].r].dis + 1;return A;
}int pop(int x)
{int l = N[x].l;int r = N[x].r;N[l].fa = l;///N[r].fa = r;///return Merge(l, r);
}int main ()
{int n, m;int x, y, fax, fay;while (scanf("%d", &n) != EOF){Init(n);scanf("%d", &m);while (m--){scanf("%d%d",&x, &y);fax = findset(x); fay = findset(y);if (fax == fay) printf("-1\n");else{int A = pop(fax);Newnode(fax, N[fax].v / 2);A = Merge(A, fax);int B = pop(fay);Newnode(fay, N[fay].v / 2);B = Merge(B, fay);printf("%d\n", N[Merge(A, B)].v);}}}return 0;
}