题目传送门
https://lydsy.com/JudgeOnline/problem.php?id=3123
题解
如果是静态的查询操作，那么就是直接树上主席树的板子。
但是我们现在有了一个连接两棵树的操作。
那么我们就采取启发式合并的方法来暴力重新建主席树。
对于表示树上前缀和的主席树来说，连接两条边以后，会影响到的点只有其中的一棵树。
所以不妨把较小的那一棵树暴力重新建立主席树。
另外由于树形态不固定，所以要用倍增 lca。
时间复杂度 \(O(n\log^2n)\)，空间复杂度 \(O(q\log^n)\)。（也许垃圾节点回收可以做做到一个 \(log\) ？）
输入的第一个数据不是数据组数！！！被坑了好久。
#include<bits/stdc++.h>
#define fec(i, x, y) (int i = head[x], y = g[i].to; i; i = g[i].ne, y = g[i].to)
#define dbg(...) fprintf(stderr, __VA_ARGS__)
#define File(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define fi first
#define se second
#define pb push_back
template<typename A, typename B> inline char smax(A &a, const B &b) {return a < b ? a = b, 1 : 0;}
template<typename A, typename B> inline char smin(A &a, const B &b) {return b < a ? a = b, 1 : 0;}
typedef long long ll; typedef unsigned long long ull; typedef std::pair<int, int> pii;
template<typename I> inline void read(I &x) {
int f = 0, c;
while (!isdigit(c = getchar())) c == '-' ? f = 1 : 0;
x = c & 15;
while (isdigit(c = getchar())) x = (x << 1) + (x << 3) + (c & 15);
f ? x = -x : 0;
}
const int N = 8e4 + 7;
const int LOG = 18;
int n, m, Q, nod, dis, la;
int a[N], b[N], f[N][LOG], dep[N], siz[N], fa[N], rt[N];
struct Edge { int to, ne; } g[N << 1]; int head[N], tot;
inline void addedge(int x, int y) { g[++tot].to = y, g[tot].ne = head[x], head[x] = tot; }
inline void adde(int x, int y) { addedge(x, y), addedge(y, x); }
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
struct Node { int lc, rc, val; } t[N * 16 * 16];
inline void ins(int &o, int p, int L, int R, int x) {
// dbg("o = %d, p = %d, L = %d, R = %d, x = %d\n", o, p, L, R, x);
t[o = ++nod] = t[p], ++t[o].val;
if (L == R) return;
int M = (L + R) >> 1;
if (x <= M) ins(t[o].lc, t[p].lc, L, M, x);
else ins(t[o].rc, t[p].rc, M + 1, R, x);
}
inline int qval(int o1, int o2, int p1, int p2, int L, int R, int k) {
// dbg("o1 = %d, o2 = %d, p1 = %d, p2 = %d, L = %d, R = %d, k = %d, t[o1].val = %d, t[o2].val = %d, t[p1].val = %d, t[p2].val = %d\n", o1, o2, p1, p2, L, R, k, t[o1].val, t[o2].val, t[p1].val, t[p2].val);
if (L == R) return L;
int M = (L + R) >> 1, ls = t[t[o1].lc].val + t[t[o2].lc].val - t[t[p1].lc].val - t[t[p2].lc].val;
if (k <= ls) return qval(t[o1].lc, t[o2].lc, t[p1].lc, t[p2].lc, L, M, k);
else return qval(t[o1].rc, t[o2].rc, t[p1].rc, t[p2].rc, M + 1, R, k - ls);
}
inline void dfs(int x, int rt, int fa = 0) {
// dbg("x = %d, rt = %d, fa = %d\n", x, rt, fa);
dep[x] = dep[fa] + 1, f[x][0] = fa, siz[x] = 1;
ins(::rt[x], ::rt[fa], 1, dis, a[x]);
if (rt) ::fa[x] = rt;
for (int i = 1; i < LOG; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
for fec(i, x, y) if (y != fa) dfs(y, rt, x), siz[x] += siz[y];
}
inline int lca(int x, int y) {
if (dep[x] < dep[y]) std::swap(x, y);
for (int i = LOG - 1; ~i; --i) if (dep[f[x][i]] >= dep[y]) x = f[x][i];
if (x == y) return x;
for (int i = LOG - 1; ~i; --i) if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
inline void lsh() {
std::sort(b + 1, b + n + 1);
dis = std::unique(b + 1, b + n + 1) - b - 1;
for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(b + 1, b + dis + 1, a[i]) - b;
}
inline void work() {
lsh();
for (int i = 1; i <= n; ++i) if (!dep[i]) dfs(i, i);
// dbg("***********\n");
while (Q--) {
char opt[5];
scanf("%s", opt);
if (*opt == 'Q') {
int x, y, k, p;
read(x), read(y), read(k);
x ^= la, y ^= la, k ^= la;
p = lca(x, y);
// dbg("x = %d, y = %d, k = %d, p = %d, la = %d\n", x, y, k, p, la);
printf("%d\n", la = b[qval(rt[x], rt[y], rt[p], rt[f[p][0]], 1, dis, k)]);
} else {
int x, y, fx, fy;
read(x), read(y);
x ^= la, y ^= la;
fx = find(x), fy = find(y);
// dbg("siz[fx] = %d, siz[fy] = %d\n", siz[fx], siz[fy]);
if (siz[fx] > siz[fy]) {
fa[fy] = fx, siz[fx] += siz[fy];
dfs(y, 0, x), adde(x, y);
} else {
fa[fx] = fy, siz[fy] += siz[fx];
dfs(x, 0, y), adde(x, y);
}
}
}
}
inline void init() {
read(n), read(m), read(Q);
for (int i = 1; i <= n; ++i) read(a[i]), b[i] = a[i];
int x, y;
for (int i = 1; i <= m; ++i) read(x), read(y), adde(x, y);
}
int main() {
#ifdef hzhkk
freopen("hkk.in", "r", stdin);
#endif
read(n);
init();
work();
fclose(stdin), fclose(stdout);
return 0;
}