[BZOJ2733][HNOI2012永無鄉][線段樹合并+并查集]

[BZOJ2733][HNOI2012永無鄉]

題目大意：

有一些島嶼，一開始由一些無向邊連接配接。後來也有不斷的無向邊加入，每一個島嶼有個一獨一無二的重要度，問任意時刻的與一個島嶼聯通的所有島中重要度第k大的島的編号是什麼。

思路：

線段樹合并裸題。

用并查集維護島嶼之間的連通性，對一個聯通塊内的島嶼建一棵權值線段樹，合并聯通塊的同時合并兩棵線段樹。

抄了 學習了一發黃學長的線段樹合并的闆子。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int Maxn = ;
int fa[Maxn], v[Maxn], id[Maxn];
inline char get(void) {
    static char buf[], *p1 = buf, *p2 = buf;
    if (p1 == p2) {
        p2 = (p1 = buf) + fread(buf, , , stdin);
        if (p1 == p2) return EOF;
    }
    return *p1++;
}
inline void read(int &x) {
    x = ; static char c; bool minus = false;
    for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') minus = true;
    for (; c >= '0' && c <= '9'; x = x *  + c - '0', c = get()); if (minus) x = -x;
}
inline void read(char &x) {
    x = get();
    while (!(x >= 'A' && x <= 'Z')) x = get();
}
inline int getf(int x) {
    return fa[x] = (x == fa[x] ? x : getf(fa[x]));
}
int root[Maxn * ], ls[Maxn * ], rs[Maxn * ], sum[Maxn * ], sz;
inline void insert(int &o, int l, int r, int val) {
    if (!o) o = ++sz;
    if (l == r) return (void)(sum[o] = );
    int mid = (l + r) >> ;
    if (mid >= val) insert(ls[o], l, mid, val);
    else insert(rs[o], mid + , r, val);
    sum[o] = sum[ls[o]] + sum[rs[o]];
}
inline int query(int o, int l, int r, int rank) {
    if (l >= r) return l;
    int mid = (l + r) >> ;
    if (sum[ls[o]] >= rank) return query(ls[o], l, mid, rank);
    else return query(rs[o], mid + , r, rank - sum[ls[o]]);
}
inline int merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    ls[x] = merge(ls[x], ls[y]);
    rs[x] = merge(rs[x], rs[y]);
    sum[x] = sum[ls[x]] + sum[rs[x]];
    return x;
}
int n, m, k;
int main(void) {
  // freopen("in.txt", "r", stdin);
    read(n), read(m);
    for (int i = ; i <= n; i++) read(v[i]);
    for (int i = ; i <= n; i++) fa[i] = i;
    for (int i = , x, y; i <= m; i++) {
        read(x), read(y);
    x = getf(x), y = getf(y);
        fa[x] = y;
    }
    for (int i = ; i <= n; i++) {
      insert(root[getf(i)], , n, v[i]);
      id[v[i]] = i;
    }
    read(k); char op; int x, y, p, q;
    while (k--) {
        read(op); read(x), read(y);
        if (op == 'Q') {
            p = getf(x);
            if (sum[root[p]] < y) {
                puts("-1");
                continue;
            }
            printf("%d\n", id[query(root[p], , n, y)]);
        } else {
            p = getf(x), q = getf(y);
            if (p == q) continue;
            fa[p] = q;
            root[q]= merge(root[p], root[q]);
        }
    }
    return ;
}
           

完。

By g1n0st