Description

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

Solution

​ 把边从小到大排序插入\(kruskal\)重构树中，对于每次询问， 倍增求出\(~v~\)祖先中第一个小于\(~x~\)的瓶颈，子树第\(~k~\)大用主席树维护即可，只不过主席树记的是第\(~k~\)小的值，记得要反过来查询。

Code

#include<bits/stdc++.h>

#define For(i, j, k) for(int i = j; i <= k; ++i)

#define Forr(i, j, k) for(int i = j; i >= k; --i)

#define Travel(i, u) for(int i = beg[u], v = to[i]; i; i = nex[i], v = to[i])

using namespace std;

inline int read() {

	int x = 0, p = 1; char c = getchar();

	for(; !isdigit(c); c = getchar()) if(c == '-') p = -1;

	for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

	return x *= p;

}

inline void File() {

#ifndef ONLINE_JUDGE

	freopen("bzoj3545.in", "r", stdin);

	freopen("bzoj3545.out", "w", stdout);

#endif

}

const int N = 2e5 + 10, M = N << 2, MAXE = 5e5 + 10;

int n, m, q, st[N], ed[N], h[N], F[20][N], cnt, clk, ls[N], lstans;

int e = 1, beg[N], nex[M], to[M], fa[N], pos[N], rt[N], tot, hh[N], id[N];

struct edge { int u, v, w; } E[MAXE];

inline void add(int x, int y) { to[++ e] = y, nex[e] = beg[x], beg[x] = e; }

inline bool cmp(const edge &a, const edge &b) { return a.w < b.w; }

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

inline void dfs(int u, int f) { pos[st[u] = ++ clk] = u; Travel(i, u) dfs(v, u); ed[u] = clk; }

inline void rebuild() {

	For(i, 1, n << 1) fa[i] = id[i] = i;

	For(i, 1, m) E[i].u = read(), E[i].v = read(), E[i].w = read();

	sort(E + 1, E + 1 + m, cmp);	

	For(i, 1, m) {

		int u = E[i].u, v = E[i].v;

		if (find(u) == find(v)) continue;

		u = fa[u], v = fa[v], hh[++ cnt] = E[i].w;

		add(cnt, u), add(cnt, v); fa[u] = fa[v] = cnt;

		F[0][u] = F[0][v] = cnt;

	}

	F[0][cnt] = cnt; dfs(cnt, cnt);

}

namespace Segment_Tree {

#define mid (l + r >> 1)

	int c = 0; struct node { int lc, rc, v; } tr[N * 30];

	inline void update(int &now, int pre, int l, int r, int rk) {

		now = ++ c, tr[now] = tr[pre], ++ tr[now].v;

		if (l < r) {

			if (rk <= mid)

				update(tr[now].lc, tr[pre].lc, l, mid, rk);

			else

				update(tr[now].rc, tr[pre].rc, mid + 1, r, rk);

		}

	}

	inline int query(int u, int v, int l, int r, int rk) {

		if (l == r) return l;

		int num = tr[tr[v].lc].v - tr[tr[u].lc].v;

		if (rk <= num)

			return query(tr[u].lc, tr[v].lc, l, mid, rk);

		else

			return query(tr[u].rc, tr[v].rc, mid + 1, r, rk - num);

	}

#undef mid

}

using namespace Segment_Tree;

inline void LS() {

	sort(ls + 1, ls + 1 + n);

	tot = unique(ls + 1, ls + 1 + n) - ls - 1;

	For(i, 1, n) h[i] = lower_bound(ls + 1, ls + 1 + tot, h[i]) - ls;

	For(i, 1, cnt) {

		if (pos[i] <= n)

			update(rt[i], rt[i - 1], 1, tot, h[pos[i]]);

		else

			rt[i] = rt[i - 1];

	}

	For(j, 1, 18) For(i, 1, cnt) F[j][i] = F[j - 1][F[j - 1][i]];

}		

int main() {

	File();

	cnt = n = read(), m = read(), q = read();

	For(i, 1, n) ls[i] = h[i] = read();

	rebuild(), LS();

	while (q --) {

		int v = read(), x = read(), k = read();

		if (lstans != -1) v ^= lstans, x ^= lstans, k ^= lstans;

		Forr(i, 18, 0) if (hh[F[i][v]] <= x) v = F[i][v];	

		int res = tr[rt[ed[v]]].v - tr[rt[st[v] - 1]].v;

		if (res < k) puts("-1"), lstans = -1;

		else {

			lstans = ls[query(rt[st[v] - 1], rt[ed[v]], 1, tot, res - k + 1)];

			printf("%d\n" ,lstans);

		}

	}

	return 0;

}