@[Svemit](/user/503792) $104$ 行，$n \to size_{hs}$ 就过了 /kel
by _sunkuangzheng_ @ 2023-10-06 20:57:27
@[_sunkuangzheng_](/user/923947) thx，已经调出来了，但是加强版没过/ng（
by Svemit @ 2023-10-06 21:00:35
@[Svemit](/user/503792) 加强版要判图不连通 /kk
by _sunkuangzheng_ @ 2023-10-06 21:01:01
@[_sunkuangzheng_](/user/923947) 没过/fad
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 5e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
int h[N];
vector<int> hs;
array<int, 3> edge[M];
vector<int> e[N];
int val[N], fa[N][25], p[N], L[N], R[N], dep[N];
struct DSU {
int fa[N];
void init() {
for(int i = 1; i <= n * 2; i ++) fa[i] = i;
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
} dsu;
int tot, idx;
void dfs(int u, int fath) {
L[u] = idx;
if(u <= n) p[++ idx] = u;
dep[u] = dep[fath] + 1;
fa[u][0] = fath;
for(int i = 1; i <= __lg(dep[u]); i ++)
fa[u][i] = fa[fa[u][i - 1]][i - 1];
for(auto v : e[u]) dfs(v, u);
R[u] = idx;
}
struct SegT {
int l, r, val;
#define l(x) tr[x].l
#define r(x) tr[x].r
#define val(x) tr[x].val
} tr[N << 5];
int rt[N], cnt;
void pushup(int x) {
val(x) = val(l(x)) + val(r(x));
}
void build(int &x, int l, int r) {
x = ++ cnt;
if(l == r) return;
int mid = l + r >> 1;
build(l(x), l, mid), build(r(x), mid + 1, r);
}
void insert(int &x, int lst, int pos, int l, int r) {
x = ++ cnt;
tr[x] = tr[lst];
if(l == r) {
val(x) ++;
return;
}
int mid = l + r >> 1;
if(pos <= mid) insert(l(x), l(lst), pos, l, mid);
else insert(r(x), r(lst), pos, mid + 1, r);
pushup(x);
}
int query(int x, int y, int l, int r, int k) {
if(l == r) return l;
int cnt = val(r(y)) - val(r(x)), mid = l + r >> 1;
if(k <= cnt) return query(r(x), r(y), mid + 1, r, k);
else return query(l(x), l(y), l, mid, k - cnt);
}
int get(int u, int x) {
for(int i = 19; ~i; i --)
if(val[fa[u][i]] <= x) u = fa[u][i];
return u;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m >> q;
for(int i = 1; i <= n; i ++) {
cin >> h[i];
hs.push_back(h[i]);
}
sort(hs.begin(), hs.end());
hs.erase(unique(hs.begin(), hs.end()), hs.end());
for(int i = 1; i <= n; i ++) {
h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin() + 1;
}
tot = n;
dsu.init();
for(int i = 1; i <= m; i ++)
cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
sort(edge + 1, edge + 1 + m);
for(int i = 1; i <= m; i ++) {
int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
if(u == v) continue;
tot ++;
dsu.fa[u] = dsu.fa[v] = tot;
e[tot].push_back(u);
e[tot].push_back(v);
val[tot] = edge[i][0];
}
val[0] = INF;
for(int i = tot; i >= 1; i --)
if(dsu.fa[i] == i) dfs(i, 0);
build(rt[0], 1, hs.size());
for(int i = 1; i <= n; i ++) {
insert(rt[i], rt[i - 1], h[p[i]], 1, hs.size());
}
int lst = 0;
while(q --) {
int v, x, k;
cin >> v >> x >> k;
v = (v ^ lst) % n + 1;
k = (k ^ lst) % n + 1;
x ^= lst;
v = get(v, x);
if(R[v] - L[v] < k) cout << -1 << '\n';
else cout << hs[query(rt[L[v]], rt[R[v]], 1, hs.size(), k) - 1] << '\n';
}
return 0;
}
```
by Svemit @ 2023-10-06 21:04:20
@[_sunkuangzheng_](/user/923947) 已经过了，thx
by Svemit @ 2023-10-06 21:17:08