题目地址：BZOJ：Problem 3551. — [ONTAK2010]Peaks加强版

题目描述

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

题意简述

有一个图，点和边都有权值。回答若干询问，每个询问表示只保留图中边权不大于x的边，v所在的连通块中，点权k大。强制在线。

输入输出格式

输入格式：
第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。v=v xor lastans，x=x xor lastans，k=k xor lastans。如果lastans=-1则不变。

输出格式：
对于每组询问，输出一个整数表示答案。

输入输出样例

输入样例#1：

10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
7 3 0
0 4 9
9 8 3

输出样例#1：

6
1
-1
8

说明

【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

题解

参考资料：BZOJ 3551: [ONTAK2010]Peaks加强版 [Kruskal重构树 dfs序 主席树] – Candy? – 博客园
强制在线之前的离线做法就不行了。这里要用新的科技：Kruskal重构树。
首先，连通块的边肯定在最小生成树上比较优，因此我们可以跑一波Kruskal处理。在Kruskal选中一条边的时候，对这条边开一个点，把边权放在点上，再从点引出两条边，指向边的端点的并查集集合代表元，将这条边的点设为这两个集合的并集代表元。
这样建出来的树有优秀的性质：

1. 二叉树，因为边有两个端点
2. 越浅的边点边权越大
3. 叶子（无出边的点）是原图中的点，其他的都是边点
4. 两点间路径上边权最大的边点是LCA
5. 一个边点对应的子树代表一个边权不大于该边点的边组成的连通块
6. 边权最大的边点是有根树的根

这里我们会用到第5条。一个查询就是在找v的边权不大于询问的最浅边点祖先，在该祖先的子树内找k大，这个显然可以DFS序建主席树做。
注意本地开够栈，DFS的规模会相当大。复杂度是O(n \log n)。

代码

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

#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();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 200005, MAXM = 500005;

int n, m, q, N;

int fa[MAXN];

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

struct Node {
    int lch, rch, val;
} tr[MAXN << 4];
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 o1, int o2, int l, int r, int k) {
    if(l == r) return l;
    int mid = (l + r) >> 1, rsiz = tr[tr[o2].rch].val - tr[tr[o1].rch].val;
    if(k <= rsiz) return query(tr[o1].rch, tr[o2].rch, mid + 1, r, k);
    else return query(tr[o1].lch, tr[o2].lch, l, mid, k - rsiz);
}

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

struct Edge {
    int u, v, w;
} edges[MAXM];

inline bool cmp(Edge a, Edge b) {
    return a.w < b.w;
}

inline void kruskal() {
    int cnt = 0;
    for(int i = 1; i <= m; i++) {
        int u = edges[i].u, v = edges[i].v, fu = find(u), fv = find(v);
        if(fu == fv) continue;
        w[++N] = edges[i].w;
        gra[N].push_back(fu); gra[N].push_back(fv);
        fa[fu] = fa[fv] = fa[N] = N;
        if(++cnt == n - 1) break;
    }
}

int vn[MAXN], dep[MAXN], dfl[MAXN], dfr[MAXN], clk;

inline void dfs(int u) {
    dfl[u] = clk;
    if(u <= n) vn[++clk] = u;
    for(int i = 1; (1 << i) <= dep[u]; i++) {
        anc[u][i] = anc[anc[u][i - 1]][i - 1];
    }
    for(int i = 0; i < gra[u].size(); i++) {
        int v = gra[u][i];
        if(v == anc[u][0]) continue;
        dep[v] = dep[u] + 1;
        anc[v][0] = u;
        dfs(v);
    }
    dfr[u] = clk;
}

inline int findrt(int u, int x) {
    for(int i = 19; i >= 0; i--) {
        if(anc[u][i] && w[anc[u][i]] <= x) u = anc[u][i];
    }
    return u;
}

std::vector<int> tmp;

int main() {
    n = readint(); m = readint(); q = readint(); N = n;
    for(int i = 1; i <= n; i++) {
        fa[i] = i; 
    }
    tmp.push_back(-1);
    for(int i = 1; i <= n; i++) {
        w[i] = readint();
        tmp.push_back(w[i]);
    }
    for(int i = 1; i <= m; i++) {
        edges[i].u = readint(); edges[i].v = readint(); edges[i].w = readint();
    }
    std::sort(edges + 1, edges + m + 1, cmp);
    kruskal();
    dfs(N);
    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 <= n; i++) {
        rt[i] = rt[i - 1];
        insert(rt[i], 1, n, w[vn[i]]);
    }
    int lastans = 0, v, x, k;
    while(q--) {
        v = readint() ^ lastans; x = readint() ^ lastans; k = readint() ^ lastans;
        v = findrt(v, x);
        if(tr[rt[dfr[v]]].val - tr[rt[dfl[v]]].val < k) puts("-1"), lastans = 0;
        else printf("%d\n", lastans = tmp[query(rt[dfl[v]], rt[dfr[v]], 1, n, k)]);
    }
    return 0;
}