bzoj 3123
题意：小$Z$有一片森林，含有$N$个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有$M$条边。
小Z希望执行$T$个操作，操作有两类：
Q x y k查询点$x$到点$y$路径上所有的权值中，第$k$小的权值是多少。此操作保证点$x$和点$y$连通，同时这两个节点的路径上至少有$k$个点。L x y在点$x$和点$y$之间连接一条边。保证完成此操作后，仍然是一片森林。
这题查询$k$小值点，显然主席树。
考虑怎么处理合并两棵树。我们想到了LCT。但是这题我们完全可以启发式合并。
每次合并两个集合，然后对小的集合重新算倍增、深度等
注意本题是合并的时候再建链，而不是先建链再合并，否则会合并很多次，造成数据重复
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const int MAXN = 100000 + 1, LOGS = 20;
int tmp, n, m, Q, val_o[MAXN], ls[MAXN];
vector<int > G_o[MAXN];
int f_o[MAXN], siz_o[MAXN], pre_o[MAXN][LOGS + 2], sz, dep_o[MAXN];
int find(int x) {return x == f_o[x] ? x : f_o[x] = find(f_o[x]);}
void ins(int u, int v) {G_o[u].push_back(v);}
#define M ((l + r) >> 1)
int lc[MAXN * 20], rc[MAXN * 20], rt_o[MAXN], sumv[MAXN * 20];
void update(int l, int r, int p, int &now, int pre) {
if (!now) now = ++sz;
sumv[now] = sumv[pre] + 1;
if (l == r) return ;
if (p <= M) rc[now] = rc[pre], update(l, M, p, lc[now], lc[pre]);
else lc[now] = lc[pre], update(M + 1, r, p, rc[now], rc[pre]);
}
void dfs(int u, int fa) {
pre_o[u][0] = fa, dep_o[u] = dep_o[fa] + 1;
for (int i = 1; i <= LOGS; ++i) pre_o[u][i] = pre_o[pre_o[u][i - 1]][i - 1];
update(1, tmp, val_o[u], rt_o[u], rt_o[fa]);
for (int i = 0; i < (int)G_o[u].size(); ++i) {
int v = G_o[u][i];
if (v != fa) dfs(v, u);
}
}
int LCA(int a, int b) {
if (dep_o[a] < dep_o[b]) swap(a, b);
for (int i = LOGS; i >= 0; --i) if (dep_o[pre_o[a][i]] >= dep_o[b]) a = pre_o[a][i];
if (a == b) return a;
for (int i = LOGS; i >= 0; --i) if (pre_o[a][i] != pre_o[b][i]) a = pre_o[a][i], b = pre_o[b][i];
return pre_o[a][0];
}
int query(int l, int r, int x, int y, int lca, int flca, int kth) {
if (l == r) return ls[l];
int sum = sumv[lc[x]] + sumv[lc[y]] - sumv[lc[lca]] - sumv[lc[flca]];
if (sum >= kth) return query(l, M, lc[x], lc[y], lc[lca], lc[flca], kth);
else return query(M + 1, r, rc[x], rc[y], rc[lca], rc[flca], kth - sum);
}
void clean() {
sz = 0, ms(f_o, 0), ms(siz_o, 0), ms(pre_o, 0);
ms(lc, 0), ms(rc, 0), ms(rt_o, 0), ms(sumv, 0);
for (int i = 0; i <= n; ++i) G_o[i].clear();
}
int solve() {
scanf("%d%d%d", &n, &m, &Q);
clean();
for (int i = 1; i <= n; ++i) scanf("%d", &val_o[i]), ls[i] = val_o[i], siz_o[i] = 0, f_o[i] = i;
sort(ls + 1, ls + 1 + n);
tmp = unique(ls + 1, ls + 1 + n) - ls - 1;
for (int i = 1; i <= n; ++i) val_o[i] = lower_bound(ls + 1, ls + 1 + tmp, val_o[i]) - ls;
for (int u, v, i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
int x = find(u), y = find(v);
f_o[x] = y, siz_o[y] += siz_o[x];
}
for (int u = 1; u <= n; ++u) if (u == find(u)) dfs(u, 0);
int la = 0; char s[5];
while (Q--) {
scanf("%s", s);
if (s[0] == 'Q') {
int x, y, k; scanf("%d%d%d", &x, &y, &k);
x ^= la, y ^= la, k ^= la;
int l = LCA(x, y);
printf("%d\n", la = query(1, tmp, rt_o[x], rt_o[y], rt_o[l], rt_o[pre_o[l][0]], k));
} else {
int x, y; scanf("%d%d", &x, &y);
x ^= la, y ^= la;
int a = find(x), b = find(y);
if (siz_o[a] > siz_o[b]) swap(a, b), swap(x, y);
f_o[a] = b, siz_o[b] += siz_o[a];
ins(x, y), ins(y, x), dfs(x, y);
}
}
return 0;
}
}
int main() {
int T;
while (scanf("%d", &T) == 1) flyinthesky::solve();
return 0;
}
