森林中有 个点， 条边，每个点有点权，执行 次操作：
- 查询两点间点权的第 小；
- 连接两个点，保证图在操作后仍然为森林。
链接
题解
对于第 小的询问，可以使用类似树上前缀和求两点距离的方法，使用主席树。将主席树的序列前缀和改为树上前缀和即可。
对于合并操作，每次将较小树合并到较大树上（使用并查集维护每棵树的大小），可以证明总复杂度为 。
代码
#pragma GCC optimize("O3")
#include <cstdio>
#include <algorithm>
#include <queue>
#define inline inline __attribute__((always_inline))
const int MAXN = 80000;
const int MAXN_LOG = 17;
struct UnionFindSet {
int a[MAXN], s[MAXN];
inline void init(const int n) { for (register int i = 0; i < n; i++) a[i] = i, s[i] = 1; }
int find(const int x) { return x == a[x] ? x : a[x] = find(a[x]); }
inline int getSize(const int x) { return s[find(x)]; }
inline void merge(const int x, const int y) {
const register int p = find(x), q = find(y);
a[p] = q;
s[q] += s[p];
}
} ufs;
struct SegmentTree {
int l, r;
SegmentTree *lc, *rc;
int cnt, refCnt;
inline SegmentTree(const int l, const int r, SegmentTree *lc = NULL, SegmentTree *rc = NULL, const int cnt = 0) : l(l), r(r), lc(lc), rc(rc), cnt(cnt), refCnt(1) {}
inline static SegmentTree *newNode();
inline static void deleteNode(SegmentTree *v);
~SegmentTree() {
if (r - l < 600) return;
if (lc && lc->unref()) deleteNode(lc);
if (rc && rc->unref()) deleteNode(rc);
}
inline SegmentTree *buildChild(const int x) {
register int mid = l + (r - l) / 2;
if (x <= mid) return new (newNode()) SegmentTree(l, mid, NULL, NULL, 0);
else return new (newNode()) SegmentTree(mid + 1, r, NULL, NULL, 0);
}
SegmentTree *insertSelf(const int x) {
cnt++;
register int mid = l + (r - l) / 2;
if (x == l && x == r) return this;
else if (x <= mid) return (lc = buildChild(x))->insertSelf(x), this;
else return (rc = buildChild(x))->insertSelf(x), this;
}
SegmentTree *insert(const int x) {
register int mid = l + (r - l) / 2;
if (x == l && x == r) return new (newNode()) SegmentTree(l, r, NULL, NULL, cnt + 1);
else if (x <= mid) return new (newNode()) SegmentTree(l, r, lc ? lc->insert(x) : buildChild(x)->insertSelf(x), rc ? rc->ref() : NULL, cnt + 1);
else return new (newNode()) SegmentTree(l, r, lc ? lc->ref() : NULL, rc ? rc->insert(x) : buildChild(x)->insertSelf(x), cnt + 1);
}
inline SegmentTree *ref() {
refCnt++;
return this;
}
inline bool unref() {
return !--refCnt;
}
int query(const int l, const int r) {
if (l > this->r || r < this->l) return 0;
else if (l <= this->l && r >= this->r) return cnt;
else return lc->query(l, r) + rc->query(l, r);
}
inline int rank() {
return lc ? lc->cnt : 0;
}
} *segRoot;
template <typename T, size_t SIZE>
struct MemoryPool {
char buf[sizeof(T) * SIZE], *p;
T *recycle[SIZE], **pr;
inline MemoryPool() : p(buf), pr(recycle) {}
inline T *alloc() {
if (p == buf + sizeof(T) * SIZE) {
if (pr <= recycle) throw std::bad_alloc();
else return *--pr;
} else {
register char *res = p;
p += sizeof(T);
return reinterpret_cast<T *>(res);
}
}
inline void free(T *p) {
*pr++ = p;
}
};
MemoryPool<SegmentTree, MAXN * MAXN_LOG * 10> pool;
inline SegmentTree *SegmentTree::newNode() {
return pool.alloc();
}
inline void SegmentTree::deleteNode(SegmentTree *p) {
p->~SegmentTree();
pool.free(p);
}
struct Node {
struct Edge *e;
Node *p;
int w, ts, d;
bool v;
SegmentTree *seg;
Node *f[MAXN_LOG + 1];
} N[MAXN];
struct Edge {
Node *s, *t;
Edge *next;
Edge(Node *s, Node *t) : s(s), t(t), next(s->e) {};
};
inline void addEdge(const int u, const int v) {
N[u].e = new Edge(&N[u], &N[v]);
N[v].e = new Edge(&N[v], &N[u]);
}
int n, ts, logn = 0;
inline void bfs(Node *start, const bool init = true) {
++ts;
std::queue<Node *> q;
start->ts = ts;
if (init) {
start->p = start->f[0] = start;
start->seg = segRoot->insert(start->w);
start->d = 0;
}
q.push(start);
while (!q.empty()) {
Node *v = q.front();
q.pop();
for (register int j = 1; j <= logn; j++) {
v->f[j] = v->f[j - 1]->f[j - 1];
}
for (Edge *e = v->e; e; e = e->next) if (e->t->ts != ts && (init || e->t != start->p)) {
e->t->ts = ts;
e->t->p = e->t->f[0] = v;
if (e->t->seg) SegmentTree::deleteNode(e->t->seg);
e->t->seg = v->seg->insert(e->t->w);
e->t->d = v->d + 1;
q.push(e->t);
}
}
}
inline void bfs() {
for (register int i = 0; i < n; i++) if (N[i].ts == 0) bfs(&N[i]);
}
inline void link(int u, int v) {
const register int su = ufs.getSize(u), sv = ufs.getSize(v);
if (su > sv) std::swap(u, v);
addEdge(u, v);
N[u].p = N[u].f[0] = &N[v];
SegmentTree::deleteNode(N[u].seg);
N[u].seg = N[v].seg->insert(N[u].w);
N[u].d = N[v].d + 1;
bfs(&N[u], false);
ufs.merge(u, v);
}
inline Node *lca(Node *u, Node *v) {
if (u->d < v->d) std::swap(u, v);
if (u->d != v->d) {
for (register int i = logn; i >= 0; i--) if (u->f[i]->d >= v->d) u = u->f[i];
}
if (u != v) {
for (register int i = logn; i >= 0; i--) if (u->f[i] != v->f[i]) u = u->f[i], v = v->f[i];
return u->p;
}
return u;
}
inline int query(Node *u, Node *v, int k) {
Node *p = lca(u, v);
register int min = 0, max = n - 1;
SegmentTree *sa = u->seg, *sb = v->seg, *sc = p->seg, *sd = p->p != p ? p->p->seg : segRoot;
while (min != max) {
const register int mid = min + (max - min) / 2;
register int t = 0;
if (sa) t += sa->rank();
if (sb) t += sb->rank();
if (sc) t -= sc->rank();
if (sd) t -= sd->rank();
if (k <= t) {
if (sa) sa = sa->lc;
if (sb) sb = sb->lc;
if (sc) sc = sc->lc;
if (sd) sd = sd->lc;
max = mid;
} else {
if (sa) sa = sa->rc;
if (sb) sb = sb->rc;
if (sc) sc = sc->rc;
if (sd) sd = sd->rc;
k -= t, min = mid + 1;
}
}
return min;
}
int main() {
int tc;
scanf("%d", &tc);
int m, t;
scanf("%d %d %d", &n, &m, &t);
ufs.init(n);
for (; (1 << (logn + 1)) <= n; logn++);
for (register int i = 0; i < n; i++) scanf("%d", &N[i].w);
static int set[MAXN];
for (register int i = 0; i < n; i++) set[i] = N[i].w;
std::sort(set, set + n);
register int *end = std::unique(set, set + n);
for (register int i = 0; i < n; i++) N[i].w = std::lower_bound(set, end, N[i].w) - set;
segRoot = new SegmentTree(0, n - 1);
while (m--) {
int u, v;
scanf("%d %d", &u, &v), u--, v--;
addEdge(u, v);
}
bfs();
register int lastAns = 0;
while (t--) {
char cmd[2];
int u, v;
scanf("%s %d %d", cmd, &u, &v), u ^= lastAns, v ^= lastAns, u--, v--;
if (cmd[0] == 'Q') {
int k;
scanf("%d", &k);
k ^= lastAns;
printf("%d\n", lastAns = set[query(&N[u], &N[v], k)]);
} else {
link(u, v);
}
}
return 0;
}