laekov

数据结构题神马的最开心了。

乍一看动态树，其实不然。复杂度可以再乘一个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)));

}

}

}