BZOJ 3123: [Sdoi2013]森林

我以为有多组数据，原来第一个数是数据编号，绝了
只有连边操作，启发式合并即可。
然后就是主席树裸题了。
空间要开大一点，因为主席树我不知道怎么回收空间。。

#include <bits/stdc++.h>
#define l(p) tree[p].l
#define r(p) tree[p].r
#define mid ((l + r) >> 1)

namespace IO {
    inline void read() {}
    template<class T, class... T2>
    inline void read(T &x, T2 &... oth) {
        T f = 1; x = 0; char ch = getchar();
        while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
        while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar(); 
        x *= f;
        read(oth...);
    }
}

const int N = 1e5 + 7, ALL = 1e9 + 7;
int head[N], cnt = 1, to[N * 2], ne[N * 2], Fa[N], fa[N][19];
int n, m, q, root[N], dep[N], version[N], val[N];
int sz[N];

inline void add(int u, int v) {
    to[++cnt] = v; ne[cnt] = head[u]; head[u] = cnt;
}

struct Seg {
    struct Tree {
        int l, r, sum;
    } tree[N * 200];
    int tol;
    void update(int &p, int q, int l, int r, int pos) {
        tree[p = ++tol] = tree[q];
        tree[p].sum++;
        if (l == r) return;
        if (pos <= mid) update(l(p), l(q), l, mid, pos);
        else update(r(p), r(q), mid + 1, r, pos);
    }
    int query(int p, int q, int lca, int fa_lca, int l, int r, int k) {
        if (l == r) return l;
        int sum = tree[l(p)].sum + tree[l(q)].sum - tree[l(lca)].sum - tree[l(fa_lca)].sum;
        if (sum >= k) return query(l(p), l(q), l(lca), l(fa_lca), l, mid, k);
        return query(r(p), r(q), r(lca), r(fa_lca), mid + 1, r, k - sum);
    }
} seg;

void dfs(int u, int f, int F) {
    sz[F]++; Fa[u] = F; fa[u][0] = f; dep[u] = dep[f] + 1;
    for (int i = 1; i <= 17; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    seg.update(root[u], root[f], 0, ALL, val[u]);
    for (int i = head[u]; i; i = ne[i]) {
        int v = to[i];
        if (Fa[v] == F || v == f) continue;
        dfs(v, u, F);
    }
}

int Lca(int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    int dif = dep[u] - dep[v];
    for (int i = 17; ~i; i--) 
        if (dif >> i & 1)
            u = fa[u][i];
    if (u == v) return u;
    for (int i = 17; ~i; i--)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

void solve() {
    IO::read(n, m, q);
    for (int i = 1; i <= n; i++)
        IO::read(val[i]);
    for (int i = 1, u, v; i <= m; i++) {
        IO::read(u, v);
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; i++)
        if (!Fa[i]) dfs(i, 0, i);
    int ans = 0;
    for (int x, y, k; q--; ) {
        char s[3];
        scanf("%s", s);
        IO::read(x, y);
        x ^= ans, y ^= ans;
        if (s[0] == 'Q') {
            IO::read(k);
            k ^= ans;
            int ll = Lca(x, y);
            printf("%d\n", ans = seg.query(root[x], root[y], root[ll], root[fa[ll][0]], 0, ALL, k));
        } else {
            if (sz[Fa[x]] < sz[Fa[y]]) std::swap(x, y);
            add(x, y); add(y, x);
            dfs(y, x, Fa[x]);
        }
    }
}

int main() {
    int T;
    IO::read(T);
    solve();
    return 0;
}

BZOJ 3123: [Sdoi2013]森林

原文：https://www.cnblogs.com/Mrzdtz220/p/12313815.html