SDOI2013森林

题面

主席树启发式合并，每次连边维护并查集，集合大小，求lca所需信息，合并两个树上的主席树, 重点看代码.

#include <iostream>
#include <algorithm>
#include <cassert>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 8e4 + 1, M = 2e7 + 1;

int n, m, SIZE, Ht[N], a[N], T;
int head[N], nxt[N<<1], ver[N<<1], tot;

void add(int u, int v)
{ ver[++tot] = v, nxt[tot] = head[u], head[u] = tot; }

int f[N][21], dep[N];

int LCA(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = 20; i >= 0; -- i) {
        if (dep[f[u][i]] >= dep[v]) {
            u = f[u][i];
        }
    }
    assert(dep[u] == dep[v]);
    if (u == v) return u;
    for (int i = 20; i >= 0; -- i) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    assert(f[u][0] == f[v][0]);
    return f[u][0];
}

int sum[M], ls[M], rs[M], cnt, rt[N];

void insert(int &p, int l, int r, int val) {
    p = ++cnt;
    if (l == r) return;
    int mid = l + r >> 1;
    if (val <= mid) insert(ls[p], l, mid, val);
    else insert(rs[p], mid + 1, r, val);
}

void update(int last, int p, int l, int r, int val) {
    assert(p);
    sum[p] = sum[last] + 1;
    if (l ==r) return;
    int mid = l + r >> 1; 
    if (val <= mid) update(ls[last], ls[p], l, mid, val), rs[p] = rs[last];
    else update(rs[last], rs[p], mid + 1, r, val), ls[p] = ls[last];
}

int query(int last1, int last2, int p1, int p2, int l, int r, int k) {
    if (l == r) return Ht[l];
    int s = sum[ls[p1]] - sum[ls[last1]] + sum[ls[p2]] - sum[ls[last2]];
    int mid = l + r >> 1;
    if (k <= s) return query(ls[last1], ls[last2], ls[p1], ls[p2], l, mid, k);
    else return query(rs[last1], rs[last2], rs[p1], rs[p2], mid + 1, r, k - s);
}

bool vis[N];
void DFS(int u, int fa) {
    vis[u] = 1;
    update(rt[fa], rt[u], 1, SIZE, a[u]); 
    dep[u] = dep[fa] + 1;
    f[u][0] = fa;
    for (int i = 1; i <= 20; ++ i)
        f[u][i] = f[ f[u][i - 1] ][i - 1];
 
    for (int i = head[u]; i; i = nxt[i]) {
        if (ver[i] != fa) DFS(ver[i], u);
    }
}

int fa[N], size[N];
int find(int x)
{ return x == fa[x] ? x : fa[x] = find(fa[x]); }

void link(int &u, int &v) {
    add(u, v); add(v, u);
    int Fu = find(u), Fv = find(v);
    if (size[Fu] > size[Fv]) swap(u, v), swap(Fu, Fv);
    fa[Fv] = Fu; size[Fu] += size[Fv];
}

int calc(int u, int v, int k) {
    int lca = LCA(u, v);
    return query(rt[lca], rt[f[lca][0]], rt[u], rt[v], 1, SIZE, k);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("P3302.in", "r", stdin);
    freopen("P3302.out", "w", stdout);
#endif
    int _;
    scanf("%d %d %d %d", &_, &n, &m, &T);
    for (int i = 1; i <= n; ++ i) scanf("%d", a + i), Ht[i] = a[i];

    sort(Ht + 1, Ht + 1 + n);
    SIZE = unique(Ht + 1 ,Ht + 1+ n) - Ht - 1;
    for (int i = 1 ;i <= n; ++ i) a[i] = lower_bound(Ht + 1, Ht + 1 + SIZE, a[i]) - Ht;

    for (int i = 1; i <= n; ++ i) fa[i] = i, size[i] = 1, insert(rt[i], 1, SIZE, a[i]);

    for (int i = 1; i <= m; ++ i) {
        int u, v;
        scanf("%d %d", &u, &v);
        link(u, v);
    }

    for (int i = 1; i <= n; ++ i) 
        if (!vis[find(i)]) DFS(find(i), 0);

    int ans = 0;
    char op[4];
    while (T --) {
        scanf("%s", op);
        if (op[0] == 'Q') {
            int x, y, k; scanf("%d%d%d", &x, &y, &k); x ^= ans, y ^= ans, k ^= ans; printf("%d
", ans = calc(x, y, k));
        } else {
            int x, y; scanf("%d%d", &x, &y); x ^= ans, y ^= ans; link(x, y); DFS(x, y);
        }
    }
}