「BZOJ2733」「洛谷3224」「HNOI2012」永无乡【线段树合并】

时间：2021-10-09 23:15:34

题目链接

【洛谷】

题解

很明显是要用线段树合并的。
对于当前的每一个连通块都建立一个权值线段树。
权值线段树处理操作中的\(k\)大的问题。
如果需要合并，那么就线段树暴力合并，时间复杂度是\(nlogn\)，均摊下来就是\(logn\)。
判断联通性的问题就用并查集来解决。
如果在同一个联通块里，就不能合并，否则会出一点问题。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 3000000 + 6;

int rt[N], id[N], fa[N];
int n, m, v[N], k;
char opt[5];

namespace seg {
int ncnt = 0;
struct node {
    int lc, rc, sz;
    node() { lc = rc = sz = 0; }
} tr[N << 1];
void pushup(int nod) {
    tr[nod].sz = tr[tr[nod].lc].sz + tr[tr[nod].rc].sz;
}
void ins(int &nod, int l, int r, int k) {
    if (!nod) nod = ++ ncnt;
    if (l == r) {
        tr[nod].sz = 1;
        return;
    }
    int mid = (l + r) >> 1;
    if (k <= mid) ins(tr[nod].lc, l, mid, k);
    else ins(tr[nod].rc, mid + 1, r, k);
    pushup(nod);
}
int kth(int x, int l, int r, int rk) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tr[tr[x].lc].sz >= rk) return kth(tr[x].lc, l, mid, rk);
    else return kth(tr[x].rc, mid + 1, r, rk - tr[tr[x].lc].sz);
}
int merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    tr[x].lc = merge(tr[x].lc, tr[y].lc);
    tr[x].rc = merge(tr[x].rc, tr[y].rc);
    pushup(x);
    return x;
} }

int gf(int x) {
    return x == fa[x] ? x : fa[x] = gf(fa[x]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) {
        scanf("%d", &v[i]);
        fa[i] = i;
        id[v[i]] = i;
    }
    for (int i = 1, a, b; i <= m; i ++) {
        scanf("%d%d", &a, &b);
        int x = gf(a), y = gf(b);
        fa[x] = y;
    }
    for (int i = 1; i <= n; i ++) seg::ins(rt[gf(i)], 1, n, v[i]);
    scanf("%d", &k);
    while (k --) {
        scanf("%s", opt); int x, y; scanf("%d%d", &x, &y);
        if (opt[0] == 'Q') {
            int z = gf(x);
            if (seg::tr[rt[z]].sz < y) puts("-1");
            else {
                int t = seg::kth(rt[z], 1, n, y);
                printf("%d\n", id[t]);
            }
        } else {
            int a = gf(x), b = gf(y);
            if (a == b) continue;
            fa[a] = b;
            rt[b] = seg::merge(rt[a], rt[b]);
        }
    }
    return 0;
}

相关文章