程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> ZOJ 2334 Monkey King（左偏樹）

ZOJ 2334 Monkey King（左偏樹）

編輯：關於C語言

ZOJ 2334 Monkey King（左偏樹）

思路：左偏樹模板題，需要維護集合關系，這個可以用並查集很方便的維護，另外需要用一個數組來維護每個點所在的左偏樹編號。

細節參見代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 3e5 + 10;
int T,n,m;
int tot, u, a, b, v[maxn], l[maxn], r[maxn], d[maxn], p[maxn], id[maxn];
int _find(int x) { return p[x] == x ? x : p[x] = _find(p[x]); }
int Merge(int x, int y) {
    if(!x) return y;
    if(!y) return x;
    if(v[x] < v[y]) swap(x, y);
    r[x] = Merge(r[x], y);
    if(d[l[x]] < d[r[x]]) swap(l[x], r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}
int init(int x) {
    tot++;
    v[tot] = x;
    l[tot] = r[tot] = d[tot] = 0;
    return tot;
}
int Insert(int x, int y) {
    return Merge(x, init(y));
}
int top(int x) {
    return v[x];
}
int pop(int x) {
    return Merge(l[x], r[x]);
}
int main() {
    while(~scanf("%d",&n)) {
        tot = 0;
        for(int i = 1; i <= n; i++) {
            p[i] = i;
            id[i] = i;
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d",&u);
            init(u);
        }
        scanf("%d",&m);
        while(m--) {
            scanf("%d%d",&a,&b);
            int x = _find(a), y = _find(b);
            if(x == y) printf("-1\n");
            else {
                int u = top(id[x]);
                id[x] = pop(id[x]);
                id[x] = Insert(id[x], u/2);
                u = top(id[y]);
                id[y] = pop(id[y]);
                id[y] = Insert(id[y], u/2);
                p[x] = y;
                id[y] = Merge(id[x], id[y]);
                u = top(id[y]);
                printf("%d\n",u);
            }
        }
    }
    return 0;
}