重要的事情说三遍
不保证图联通
不保证图联通
不保证图联通
那些和我一样认为重构树是点数的童鞋是要GG
Description
【题目描述】同3545
Input
第一行三个数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则不变。
Output
同3545
Sample Input
Sample Output
HINT
【数据范围】同3545
思路
bzoj3545强制在线版本
数据鬼畜
然后大概造数据的人没考虑这个问题
直接kruskal重构树跑一下
然后因为kruskal重构树是二叉堆
所以可以到达的点就变成了一个子树
然后就直接先倍增再用主席树可持久化一下dfs序查询区间第k大就可以了
#include<bits/stdc++.h>
using namespace std;
int read() {
int res = 0; char c = getchar();
while (!isdigit(c)) c = getchar();
while (isdigit(c)) res = res * 10 + c - '0', c = getchar();
return res;
}
const int N = 2e5 + 10;
const int M = 5e5 + 10;
struct Edge {
int u, v, w, nxt;
bool operator < (const Edge &b) const {
return w < b.w;
}
} P[M], E[M];
int n, m, q, pre[N], h[N], w[N];
int Fa[N], head[N], tot = 0;
int find(int x) {
return x == Fa[x] ? x : Fa[x] = find(Fa[x]);
}
void addedge(int u, int v) {
E[++tot] = (Edge) {u, v, 0, head[u]};
head[u] = tot;
}
int Kruskal() {
sort(P + 1, P + m + 1);
for (int i = 1; i <= n * 2; i++) Fa[i] = i;
int ind = n;
for (int i = 1, cnt = 0; i <= m; i++) {
int fau = find(P[i].u), fav = find(P[i].v);
if (fau == fav) continue;
++ind;
Fa[fau] = Fa[fav] = ind;
addedge(ind, fau);
addedge(ind, fav);
w[ind] = P[i].w;
if (++cnt == n - 1) break;
}
return ind;
}
int ind = 0, id[N];
int bg[N], ed[N];
int fa[N][20];
void dfs(int u, int father) {
fa[u][0] = father;
for (int i = 1; i <= 18; i++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
if (u <= n) {
id[++ind] = u;
bg[u] = ind;
} else {
bg[u] = ind + 1;
}
for (int i = head[u]; i; i = E[i].nxt) {
int v = E[i].v;
if (v == father) continue;
dfs(v, u);
}
ed[u] = ind;
}
int rt[N], ls[N * 30], rs[N * 30], siz[N * 30], cnt = 0;
void insert(int &t, int last, int l, int r, int pos) {
t = ++cnt;
siz[t] = siz[last] + 1;
if (l == r) return;
ls[t] = ls[last];
rs[t] = rs[last];
int mid = (l + r) >> 1;
if (pos <= mid) insert(ls[t], ls[last], l, mid, pos);
else insert(rs[t], rs[last], mid + 1, r, pos);
}
int query(int rtl, int rtr, int l, int r, int k) {
if (siz[rtr] - siz[rtl] < k) return -1;
if (l == r) return pre[l];
int mid = (l + r) >> 1, sizr = siz[rs[rtr]] - siz[rs[rtl]];
if (k <= sizr) return query(rs[rtl], rs[rtr], mid + 1, r, k);
else return query(ls[rtl], ls[rtr], l, mid, k - sizr);
}
int findpos(int u, int vl) {
for (int k = 18; k >= 0; k--)
if (fa[u][k] && w[fa[u][k]] <= vl) // **
u = fa[u][k];
return u;
}
int main() {
#ifdef dream_maker
freopen("input.txt", "r", stdin);
#endif
n = read(), m = read(), q = read();
for (int i = 1; i <= n; i++)
pre[i] = h[i] = read();
for (int i = 1; i <= m; i++)
P[i].u = read(), P[i].v = read(), P[i].w = read();
int root = Kruskal();
sort(pre + 1, pre + n + 1);
int num = unique(pre + 1, pre + n + 1) - pre - 1;
for (int i = 1; i <= n; i++)
h[i] = lower_bound(pre + 1, pre + num + 1, h[i]) - pre;
dfs(root, 0);
for (int i = 1; i <= n; i++)
insert(rt[i], rt[i - 1], 1, num, h[id[i]]);
int lastans = 0;
while (q--) {
int v, x, k;
scanf("%d %d %d", &v, &x, &k);
v ^= lastans, x ^= lastans, k ^= lastans;
v = findpos(v, x);
printf("%d\n", lastans = query(rt[bg[v] - 1], rt[ed[v]], 1, num, k));
if (lastans < 0) lastans = 0;
}
return 0;
}