hdu 1512 Monkey King （左偏树 实现 可并堆）
待验证
//#pragma comment(linker, /STACK:1024000000,1024000000) #include #include #include #include #include #include #include #include #include #include #include #include #include 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_pair typedef 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 ); 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[Merge(A, B)].v); } } } return 0; }