题目地址：洛谷：【P3302】[SDOI2013]森林 – 洛谷、BZOJ：Problem 3123. — [Sdoi2013]森林

题目描述

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

1. Q x y k查询点x到点y路径上所有的权值中，第k小的权值是多少。此操作保证点x和点y连通，同时这两个节点的路径上至少有k个点。
2. 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.

题意简述

给一个森林，两种操作，强制在线：

1. 查询树链权值第k大
2. 加边，保证加边后不出现环

输入输出格式

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

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

输入输出样例

输入样例#1：

1
8 4 8
1 1 2 2 3 3 4 4
4 7
1 8
2 4
2 1
Q 8 7 3 
Q 3 5 1
Q 10 0 0
L 5 4
L 3 2 
L 0 7
Q 9 2 5 
Q 6 1 6

输出样例#1：

2 
2
1
4
2

说明

对于第一个操作 Q 8 7 3，此时 lastans=0，所以真实操作为Q 8^0 7^0 3^0，也即Q 8 7 3。点8到点7的路径上一共有5个点，其权值为4 1 1 2 4。
这些权值中，第三小的为 2，输出 2，lastans变为2。
对于第二个操作 Q 3 5 1 ，此时lastans=2，所以真实操作为Q 3^2 5^2 1^2 ，也即Q 1 7 3。点1到点7的路径上一共有4个点，其权值为 1 1 2 4 。
这些权值中，第三小的为2，输出2，lastans变为 2。之后的操作类似。

题解

树链第k大可以用主席树，而动态加边可以用LCT，选择任意一种会使得另外一种操作变慢。这里不妨选择主席树，但是要考虑如何处理动态加边。
这里可以用启发式合并的思想。当加入一条边的时候，更新较小的树的信息。由于合并后的树至少是较小的树大小的两倍，我们可以保证这一操作的规模为O(\log n)。每次更新信息都需要重新更新主席树，有O(\log n)的开销，因此启发式合并的总复杂度是O(\log^2 n)的。查一个树的大小可以用并查集实现，类似并查集按秩合并。
树链查第k大的树套树就是常规的树上差分的思路，即x到y树链查询的时候，值应该由x+y-LCA-LCA的父亲这样计算出来。LCA采用倍增算法，在上面更新树信息的时候只需要在DFS的时候顺带计算一遍倍增数组就好了。
空间占用挺大的，几乎是卡着过去的，这个代码也成功在BZOJ上跑出了非常烂的成绩。只是我并查集启发式写假了QAQ，不过居然能过题，数据有点弱？

代码

// Code by KSkun, 2018/5
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>
#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) 
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool isop(char c) {
    return c == 'Q' || c == 'L';
}

inline char readop() {
    char c;
    while(!isop(c = fgc())) {}
    return c;
}

const int MAXN = 80005;

int n, m;

struct Node {
    int lch, rch, val;
} tr[MAXN * 200];
int rt[MAXN], tot;

inline void insert(int &o, int l, int r, int x) {
    tr[++tot] = tr[o]; o = tot;
    tr[o].val++;
    if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) insert(tr[o].lch, l, mid, x);
    else insert(tr[o].rch, mid + 1, r, x);
}

inline int query(int ou, int ov, int of, int off, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1, lsiz = tr[tr[ou].lch].val + tr[tr[ov].lch].val 
        - tr[tr[of].lch].val - tr[tr[off].lch].val;
    if(k <= lsiz) return query(tr[ou].lch, tr[ov].lch, tr[of].lch, tr[off].lch, l, mid, k);
    else return query(tr[ou].rch, tr[ov].rch, tr[of].rch, tr[off].rch, mid + 1, r, k - lsiz);
}

int fa[MAXN], siz[MAXN];

inline void init() {
    for(int i = 1; i <= n; i++) {
        fa[i] = i; siz[i] = 1;
    }
}

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

inline void join(int x, int y) {
    int fx = find(x), fy = find(y);
    if(fx == fy || !fx || !fy) return;
    if(siz[fx] < siz[fy]) {
        fa[fx] = fy;
        siz[fy] += siz[fx];
    } else {
        fa[fy] = fx;
        siz[fx] += siz[fy];
    }
}

int w[MAXN], anc[MAXN][20], dep[MAXN];
std::vector<int> gra[MAXN];

inline void dfs(int u, int f) {
    anc[u][0] = f; dep[u] = dep[f] + 1; join(u, f);
    for(int i = 1; i <= 19; i++) {
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    }
    rt[u] = rt[f];
    insert(rt[u], 1, n, w[u]);
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == f) continue;
        dfs(v, u);
    }
}

inline int querylca(int x, int y) {
    if(dep[x] > dep[y]) std::swap(x, y);
    int del = dep[y] - dep[x];
    for(int i = 19; i >= 0; i--) {
        if(del & (1 << i)) y = anc[y][i];
    }
    if(x == y) return x;
    for(int i = 19; i >= 0; i--) {
        if(anc[x][i] != anc[y][i]) {
            x = anc[x][i]; y = anc[y][i];
        }
    }
    return anc[x][0];
}

std::vector<int> tmp;
int q, x, y, k;
char op;

int main() {
    readint();  n = readint(); m = readint(); q = readint();
    init();
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
        tmp.push_back(w[i]);
    }
    tmp.push_back(-1);
    std::sort(tmp.begin(), tmp.end());
    tmp.erase(std::unique(tmp.begin(), tmp.end()), tmp.end());
    for(int i = 1; i <= n; i++) {
        w[i] = std::lower_bound(tmp.begin(), tmp.end(), w[i]) - tmp.begin();
    }
    for(int i = 1; i <= m; i++) {
        x = readint(); y = readint();
        gra[x].push_back(y);
        gra[y].push_back(x);
    }
    for(int i = 1; i <= n; i++) {
        if(!anc[i][0]) dfs(i, 0);
    }
    int lastans = 0;
    while(q--) {
        op = readop(); x = readint() ^ lastans; y = readint() ^ lastans;
        if(op == 'Q') {
            k = readint() ^ lastans;
            int lca = querylca(x, y);
            lastans = tmp[query(rt[x], rt[y], rt[lca], rt[anc[lca][0]], 1, n, k)];
            printf("%d\n", lastans);
        } else if(op == 'L') {
            gra[x].push_back(y); gra[y].push_back(x);
            int fx = find(x), fy = find(y);
            if(siz[fx] < siz[fy]) {
                dfs(x, y);
            } else {
                dfs(y, x);
            }
        }
    }
    return 0;
}