难度：省选/NOI-

题目描述

        小Z有一片森林，含有N个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有M条边。
        小Z希望执行T个操作，操作有两类：

  • Q x y k查询点x到点y路径上所有的权值中，第k小的权值是多少。此操作保证点x和点y连通，同时这两个节点的路径上至少有k个点。
  • L x y在点x和点y之间连接一条边。保证完成此操作后，仍然是一片森林。

        为了体现程序的在线性，我们把输入数据进行了加密。设lastans为程序上一次输出的结果，初始的时候lastans为0。
        对于一个输入的操作Q x y k,其真实操作为Q x^lastans y^lastans k^lastans。
        对于一个输入的操作L x y，其真实操作为L x^lastans y^lastans。其中^运算符表示异或，等价于pascal中的xor运算符。
        请写一个程序來帮助小Z完成这些操作。
        对于所有的数据，$n,m,T<=8*10^4$

输入格式

        第一行包含一个正整数testcase，表示当前测试数据的测试点编号。保证1<=testcase<=20。
        第二行包含三个整数N，M，T，分别表示节点数、初始边数、操作数。
        第三行包含N个非负整数表示 N个节点上的权值。
        接下来 M行，每行包含两个整数x和 y，表示初始的时候，点x和点y 之间有一条无向边。
        接下来 T行，每行描述一个操作，格式为”Q x y k“或者”L x y “，其含义见题目描述部分。

输出格式

        对于每一个第一类操作，输出一个非负整数表示答案。

题解

        看见第k小，立即想到主席树。但是本题和朴素的树上路径第k小不同的是，本题需要动态连边，问题的关键就是如何实现连边。
        在连边时，我们要考虑这两棵树连接的顺序，这里需要启发式合并：每一次都将较小的一棵树连向较大的一棵，然后在这棵小树上暴力重构主席树。可以证明，启发式合并时，每一个结点被重构的次数不会多于$logn$次，那么合并的复杂度仅为$O(logn)$，而主席树重构的复杂度为$O(nlogn)$，总复杂度$O(nlog^2n)$，对于这个数据范围来说还是可以接受的。
        在暴力重构主席树时，还需要维护lca的数组，总复杂度也是$O(nlog^2n)$。至于如何维护每一棵树的连接关系和总点数，这个可以用并查集实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>

#define N 100005
using namespace std;
struct Node {
    int l, r, v;
} nd[N << 8];
struct Edge {
    int to, next;
} edge[N << 2];
int gd[N][28], fa[N], sz[N], head[N], root[N], ts, n, m, t, v[N], tmp[N], sv, ct = 1, dep[N], last;

inline void add(int x, int y) {
    static int cnt = 1;
    edge[cnt].to = y, edge[cnt].next = head[x], head[x] = cnt++;
}

int build(int l = 1, int r = sv) {
    int p = ct++, mid = (l + r) >> 1;
    if (l == r)return p;
    nd[p].l = build(l, mid), nd[p].r = build(mid + 1, r);
    return p;
}

int ff(int x) {
    return fa[x] == x ? x : fa[x] = ff(fa[x]);
}

int newTree(int pre, int v, int l = 1, int r = sv) {
    int p = ct++, mid = (l + r) >> 1;
    nd[p] = nd[pre], ++nd[p].v;
    if (l == r)return p;
    if (v > mid)nd[p].r = newTree(nd[pre].r, v, mid + 1, r);
    else nd[p].l = newTree(nd[pre].l, v, l, mid);
    return p;
}

void DFS(int x, int pre) {
    root[x] = newTree(root[pre], lower_bound(tmp + 1, tmp + sv + 1, v[x]) - tmp);
    for (int i = head[x]; i; i = edge[i].next) {
        if (edge[i].to == pre)continue;
        dep[edge[i].to] = dep[x] + 1, gd[edge[i].to][0] = x;
        for (int p = 1; p < 25; p++)gd[edge[i].to][p] = gd[gd[edge[i].to][p - 1]][p - 1];
        DFS(edge[i].to, x);
    }
}

inline int LCA(int x, int y) {
    if (dep[x] > dep[y])swap(x, y);
    for (int i = 24; i >= 0; i--)if (dep[gd[y][i]] >= dep[x])y = gd[y][i];
    if (x == y)return x;
    for (int i = 24; i >= 0; i--)if (gd[x][i] != gd[y][i])x = gd[x][i], y = gd[y][i];
    return gd[x][0];
}

void merge(int x, int y, bool g) {//并查集合并操作
    int f1 = ff(x), f2 = ff(y);
    if (f1 == f2)return;
    else if (sz[f1] > sz[f2]) {//较小的连接较大的
        fa[f2] = f1, sz[f1] += sz[f2];
        if (g) {
            gd[y][0] = x, dep[y] = dep[x] + 1, add(x, y), add(y, x);
            for (int i = 1; i < 25; i++)gd[y][i] = gd[gd[y][i - 1]][i - 1];
            DFS(y, x);//暴力重构
        }
    } else {
        fa[f1] = f2, sz[f2] += sz[f1];
        if (g) {
            gd[x][0] = y, dep[x] = dep[y] + 1, add(x, y), add(y, x);
            for (int i = 1; i < 25; i++)gd[x][i] = gd[gd[x][i - 1]][i - 1];
            DFS(x, y);
        }
    }
}

int qu(int lca, int a, int b, int k, int obj, int l = 1, int r = sv) {
    if (l == r)return tmp[l];
    int mid = (l + r) >> 1;
    int p = nd[nd[b].l].v + nd[nd[a].l].v - 2 * nd[nd[lca].l].v + (obj >= l && obj <= mid ? 1 : 0);
    if (k <= p)return qu(nd[lca].l, nd[a].l, nd[b].l, k, obj, l, mid);
    return qu(nd[lca].r, nd[a].r, nd[b].r, k - p, obj, mid + 1, r);
}

int main() {
    scanf("%d%d%d%d", &ts, &n, &m, &t);
    for (int i = 1; i <= n; i++)fa[i] = i, scanf("%d", v + i), tmp[i] = v[i], sz[i] = 1;
    for (int i = 1, x, y; i <= m; i++)scanf("%d%d", &x, &y), add(x, y), add(y, x), merge(x, y, false);
    sort(tmp + 1, tmp + n + 1), sv = unique(tmp + 1, tmp + n + 1) - tmp - 1, root[0] = build();
    for (int i = 1; i <= n; i++)if (root[i] == 0)dep[ff(i)] = 1, DFS(ff(i), 0);
    while (t--) {
        char opt;
        int x, y, k, lca;
        scanf(" %c", &opt);
        if (opt == 'Q') {
            scanf("%d%d%d", &x, &y, &k), x ^= last, y ^= last, k ^= last, lca = LCA(x, y);
            printf("%d\n", last = qu(root[lca], root[x], root[y], k, lower_bound(tmp + 1, tmp + sv + 1, v[lca]) - tmp));
        } else if (opt == 'L')scanf("%d%d", &x, &y), x ^= last, y ^= last, merge(x, y, true);
    }
    return 0;
}