数据结构题神马的最开心了。
乍一看动态树，其实不然。复杂度可以再乘一个log的。
启发式合并。然后合并的时候直接暴力重构整棵子树，建主席树只和父亲节点有关，所以还是能搞定。
写了一个机智的垃圾回收把log^2的空间变成了log。然后发现空间有512MB。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
struct edge {
int t;
edge* next;
};
struct seg {
int v, c;
seg *ls, *rs;
};
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 80009;
const int maxl = 33;
const int maxnd = maxn * maxl;
int n, m, q, v[maxn], r[maxn], sz[maxn], tsst, maxv;
int vis[maxn], tvis;
int d[maxn], ath[maxn][maxl];
edge *head[maxn], *ep;
seg *rt[maxn], *slst[maxnd];
void init() {
ep = new edge[maxn * 2];
memset(head, 0, sizeof(head));
memset(rt, 0, sizeof(rt));
seg *sp = new seg[maxnd + 9];
for (int i = 0; i < maxnd; ++i) {
sp-> ls = 0;
sp-> rs = 0;
slst[i] = sp ++;
}
tsst = maxnd;
tvis = 0;
memset(vis, 0, sizeof(vis));
d[0] = 0;
for (int i = 0; i < maxl; ++ i)
ath[0][i] = 0;
}
inline seg* newSeg() {
seg* r = slst[-- tsst];
if (r-> ls)
if (!(-- r-> ls-> c))
slst[tsst ++] = r-> ls;
if (r-> rs)
if (!(-- r-> rs-> c))
slst[tsst ++] = r-> rs;
return r;
}
inline void addEdge(int u, int v) {
ep-> t = v;
ep-> next = head[u];
head[u] = ep ++;
}
#define vof(p) ((p)?(p->v):0)
#define lson(p) ((p)?(p->ls):0)
#define rson(p) ((p)?(p->rs):0)
seg* sgtIns(seg* q, int p0) {
seg *s = newSeg(), *p = s;
int l = 0, r = maxv + 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
p-> v = vof(q) + 1;
p-> c = 1;
if (p0 < mid) {
p-> rs = rson(q);
if (rson(q))
++ q-> rs-> c;
q = lson(q);
p-> ls = newSeg();
p = p-> ls;
r = mid;
}
else {
p-> ls = lson(q);
if (lson(q))
++ q-> ls-> c;
q = rson(q);
p-> rs = newSeg();
p = p-> rs;
l = mid;
}
}
p-> v = vof(q) + 1;
p-> c = 1;
p-> ls = 0;
p-> rs = 0;
return s;
}
int sgtKth(seg* a1, seg* a2, seg* b1, seg* b2, int k) {
int l = 0, r = maxv + 1;
while (l + 1 < r) {
int mid = (l + r) >> 1;
int t = vof(lson(a1)) + vof(lson(a2)) - vof(lson(b1)) - vof(lson(b2));
if (t >= k) {
r = mid;
a1 = lson(a1);
a2 = lson(a2);
b1 = lson(b1);
b2 = lson(b2);
}
else {
k -= t;
l = mid;
a1 = rson(a1);
a2 = rson(a2);
b1 = rson(b1);
b2 = rson(b2);
}
}
return l;
}
int getRoot(int x) {
static int stc[maxn];
int tst = 1;
stc[tst] = x;
while (stc[tst] ^ r[stc[tst]]) {
stc[tst + 1] = r[stc[tst]];
++ tst;
}
while (-- tst)
r[stc[tst]] = r[stc[tst + 1]];
return r[x];
}
void rebuild(int p0, int a) {
static int q[maxn];
int hd = 0, tl = 1;
vis[p0] = ++ tvis;
ath[p0][0] = a;
d[p0] = d[a] + 1;
q[0] = p0;
while (hd < tl) {
int p = q[hd ++];
if (rt[p])
slst[tsst ++] = rt[p], rt[p] = 0;
for (int i = 1; i < maxl; ++ i)
ath[p][i] = ath[ath[p][i - 1]][i - 1];
for (edge* e = head[p]; e; e = e-> next)
if (vis[e-> t] < tvis) {
vis[e-> t] = tvis;
d[e-> t] = d[p] + 1;
ath[e-> t][0] = p;
q[tl ++] = e-> t;
}
}
for (int ti = 0; ti < tl; ++ ti)
rt[q[ti]] = sgtIns(rt[ath[q[ti]][0]], v[q[ti]]);
}
int LCA(int u, int v) {
if (d[u] < d[v])
swap(u, v);
for (int i = maxl - 1; i >= 0; -- i)
if (d[ath[u][i]] >= d[v])
u = ath[u][i];
if (u == v)
return u;
for (int i = maxl - 1; i >= 0; -- i)
if (ath[u][i] ^ ath[v][i]) {
u = ath[u][i];
v = ath[v][i];
}
return ath[u][0];
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
init();
readInt(maxv);
readInt(n);
readInt(m);
readInt(q);
maxv = 0;
for (int i = 1; i <= n; ++ i) {
readInt(v[i]);
maxv = max(maxv, v[i]);
}
for (int i = 1; i <= n; ++ i)
r[i] = i, sz[i] = 1;
for (int i = 0; i < m; ++ i) {
int u, v;
readInt(u);
readInt(v);
addEdge(u, v);
addEdge(v, u);
u = getRoot(u);
v = getRoot(v);
sz[v] += sz[u];
r[u] = v;
}
for (int i = 1; i <= n; ++ i)
if (!rt[i])
rebuild(i, 0);
int lans = 0;
while (q --) {
char opt[2];
int u, v, k;
scanf("%s", opt);
readInt(u);
readInt(v);
u ^= lans;
v ^= lans;
if (opt[0] == 'L') {
int ru = getRoot(u), rv = getRoot(v);
if (sz[ru] < sz[rv])
swap(ru, rv), swap(u, v);
r[rv] = ru;
sz[ru] += sz[rv];
rebuild(v, u);
addEdge(u, v);
addEdge(v, u);
}
else {
readInt(k);
k ^= lans;
int a = LCA(u, v);
printf("%d\n", (lans = sgtKth(rt[u], rt[v], rt[a], rt[ath[a][0]], k)));
}
}
}