3551: [ONTAK2010]Peaks加强版

https://www.lydsy.com/JudgeOnline/problem.php?id=3551

分析：

　　kruskal重构树 +  倍增 + 主席树。

　　首先建立kruskal重构树，那么查询就变成了，在kruskal重构树上找倍增找到最上面的权值小于x的点（节点的权值为原图的边权），那么这棵树内的所有点都可以在经过权值小于x的点相互到达，所以在这棵树内查询第k大即可。dfs序后，变成序列上的问题，查询区间的第k大。

代码：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<cctype>

 #include<set>

 #include<vector>

 #include<queue>

 #include<map>

 #define fi(s) freopen(s,"r",stdin);

 #define fo(s) freopen(s,"w",stdout);

 using namespace std;

 typedef long long LL;

 inline int read() {

     int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

     for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

 }

 const int N = ;

 struct Edge{

     int u, v, w;

     bool operator < (const Edge &A) const {

         return w < A.w;

     }

 }e[];

 int fa[N << ], f[N << ][], mx[N << ], st[N << ], pos[N << ], en[N << ], val[N], disc[N]; // mx[N<<1]

 int sum[N * ], ls[N * ], rs[N * ], Root[N << ]; // 乘18，不要17

 int n, m, Q, tot, Time_Index, tot_node;

 vector<int> T[N << ];

 #define lson l, mid, rt << 1

 #define rson mid + 1, r, rt << 1 | 1

 int find(int x) {

     return x == fa[x] ? x : fa[x] = find(fa[x]);

 }

 void Kruskal() {

     for (int i=; i<=n+n; ++i) fa[i] = i;

     sort(e + , e + m + );

     int cntedge = ; tot = n;

     for (int i=; i<=m; ++i) {

         int u = find(e[i].u), v = find(e[i].v);

         if (u == v) continue;

         ++tot;

         fa[u] = tot, fa[v] = tot;

         f[u][] = tot, f[v][] = tot;

         mx[tot] = e[i].w;

         T[tot].push_back(u), T[tot].push_back(v);

 //        if (++cntedge == n + n - 1) break; // n + n - 1

     }

 }

 void dfs(int u,int fa) {

     st[u] = ++Time_Index;

     pos[Time_Index] = u;

     for (int sz=T[u].size(),i=; i<sz; ++i) {

         int v = T[u][i];

         if (v == fa) continue;

         dfs(v, u);

     }

     en[u] = Time_Index;

 }

 void update(int l,int r,int &rt,int last,int p) {

     rt = ++tot_node;

     sum[rt] = sum[last] + ;

     ls[rt] = ls[last], rs[rt] = rs[last];

     if (l == r) return ;

     int mid = (l + r) >> ;

     if (p <= mid) update(l, mid, ls[rt], ls[last], p);

     else update(mid + , r, rs[rt], rs[last], p);

 }

 int query(int l,int r,int Head,int Tail,int k) {

     if (sum[Tail] - sum[Head] < k) return -;

     if (l == r) return l;

     int mid = (l + r) >> , cnt = sum[ls[Tail]] - sum[ls[Head]];

     if (cnt >= k) return query(l, mid, ls[Head], ls[Tail], k);

     else return query(mid + , r, rs[Head], rs[Tail], k - cnt);

 }

 int main() {

     n = read(), m = read(), Q = read();

     for (int i=; i<=n; ++i) val[i] = read(), disc[i] = val[i];

     for (int i=; i<=m; ++i)

         e[i].u = read(), e[i].v = read(), e[i].w = read();

     sort(disc + , disc + n + );

     int cnt = ;

     for (int i=; i<=n; ++i) if (disc[i] != disc[cnt]) disc[++cnt] = disc[i]; // i=2

     for (int i=; i<=n; ++i) val[i] = lower_bound(disc + , disc + cnt + , val[i]) - disc;

     Kruskal();

     dfs(tot, );

     for (int j=; j<=; ++j)

         for (int i=; i<=tot; ++i) f[i][j] = f[f[i][j-]][j-];

     for (int i=; i<=tot; ++i) {

         if (pos[i] > n) Root[i] = Root[i - ];

         else update(, cnt, Root[i], Root[i - ], val[pos[i]]); // val[pos[i]] !!!

     }

     int lastans = ;

     while (Q--) {

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

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

         for (int i=; i>=; --i)

             if (f[v][i] && mx[f[v][i]] <= x) v = f[v][i];

         int l = st[v], r = en[v];

         k = sum[Root[r]] - sum[Root[l]] - k + ;

         if (k <= ) { puts("-1"); lastans = -; continue; }

         int p = query(, cnt, Root[l], Root[r], k);

         if (p == -) { puts("-1"); lastans = -; continue; }

         printf("%d\n",lastans = disc[p]);

     }

     return ;

 }