3551: [ONTAK2010]Peaks加强版

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

分析：

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

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

代码：

  1 #include<cstdio>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<iostream>
  6 #include<cctype>
  7 #include<set>
  8 #include<vector>
  9 #include<queue>
 10 #include<map>
 11 #define fi(s) freopen(s,"r",stdin);
 12 #define fo(s) freopen(s,"w",stdout);
 13 using namespace std;
 14 typedef long long LL;
 15 
 16 inline int read() {
 17     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
 18     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
 19 }
 20 
 21 const int N = 100005;
 22 
 23 struct Edge{
 24     int u, v, w;
 25     bool operator < (const Edge &A) const {
 26         return w < A.w;
 27     }    
 28 }e[500005];
 29 int fa[N << 1], f[N << 1][19], mx[N << 1], st[N << 1], pos[N << 1], en[N << 1], val[N], disc[N]; // mx[N<<1] 
 30 int sum[N * 18], ls[N * 18], rs[N * 18], Root[N << 1]; // 乘18，不要17 
 31 int n, m, Q, tot, Time_Index, tot_node;
 32 vector<int> T[N << 1];
 33 
 34 #define lson l, mid, rt << 1
 35 #define rson mid + 1, r, rt << 1 | 1
 36 
 37 int find(int x) {
 38     return x == fa[x] ? x : fa[x] = find(fa[x]);
 39 }
 40 void Kruskal() {
 41     for (int i=1; i<=n+n; ++i) fa[i] = i;
 42     sort(e + 1, e + m + 1);
 43     int cntedge = 0; tot = n;
 44     for (int i=1; i<=m; ++i) {
 45         int u = find(e[i].u), v = find(e[i].v);
 46         if (u == v) continue;
 47         ++tot;
 48         fa[u] = tot, fa[v] = tot;
 49         f[u][0] = tot, f[v][0] = tot;
 50         mx[tot] = e[i].w;
 51         T[tot].push_back(u), T[tot].push_back(v);
 52 //        if (++cntedge == n + n - 1) break; // n + n - 1
 53     }
 54 }
 55 void dfs(int u,int fa) {
 56     st[u] = ++Time_Index;
 57     pos[Time_Index] = u;
 58     for (int sz=T[u].size(),i=0; i<sz; ++i) {
 59         int v = T[u][i];
 60         if (v == fa) continue;
 61         dfs(v, u);
 62     }
 63     en[u] = Time_Index;
 64 }
 65 void update(int l,int r,int &rt,int last,int p) {
 66     rt = ++tot_node;
 67     sum[rt] = sum[last] + 1;
 68     ls[rt] = ls[last], rs[rt] = rs[last];
 69     if (l == r) return ;
 70     int mid = (l + r) >> 1;
 71     if (p <= mid) update(l, mid, ls[rt], ls[last], p);
 72     else update(mid + 1, r, rs[rt], rs[last], p);
 73 }
 74 int query(int l,int r,int Head,int Tail,int k) {
 75     if (sum[Tail] - sum[Head] < k) return -1;
 76     if (l == r) return l;
 77     int mid = (l + r) >> 1, cnt = sum[ls[Tail]] - sum[ls[Head]];
 78     if (cnt >= k) return query(l, mid, ls[Head], ls[Tail], k);
 79     else return query(mid + 1, r, rs[Head], rs[Tail], k - cnt);    
 80 }
 81 int main() {
 82     n = read(), m = read(), Q = read();
 83     for (int i=1; i<=n; ++i) val[i] = read(), disc[i] = val[i];
 84     for (int i=1; i<=m; ++i) 
 85         e[i].u = read(), e[i].v = read(), e[i].w = read();
 86     
 87     sort(disc + 1, disc + n + 1);
 88     int cnt = 1;
 89     for (int i=2; i<=n; ++i) if (disc[i] != disc[cnt]) disc[++cnt] = disc[i]; // i=2
 90     for (int i=1; i<=n; ++i) val[i] = lower_bound(disc + 1, disc + cnt + 1, val[i]) - disc;
 91     
 92     Kruskal();
 93     dfs(tot, 0);
 94     
 95     for (int j=1; j<=18; ++j) 
 96         for (int i=1; i<=tot; ++i) f[i][j] = f[f[i][j-1]][j-1];
 97     
 98     for (int i=1; i<=tot; ++i) {
 99         if (pos[i] > n) Root[i] = Root[i - 1];
100         else update(1, cnt, Root[i], Root[i - 1], val[pos[i]]); // val[pos[i]] !!!
101     }
102     
103     int lastans = 0;
104     while (Q--) {
105         int v = read(), x = read(), k = read();
106         if (lastans != -1) v ^= lastans, x ^= lastans, k ^= lastans; 
107         for (int i=18; i>=0; --i)     
108             if (f[v][i] && mx[f[v][i]] <= x) v = f[v][i];
109         int l = st[v], r = en[v];
110         k = sum[Root[r]] - sum[Root[l]] - k + 1;
111         if (k <= 0) { puts("-1"); lastans = -1; continue; }
112         int p = query(1, cnt, Root[l], Root[r], k);
113         if (p == -1) { puts("-1"); lastans = -1; continue; }
114         printf("%d
",lastans = disc[p]);
115     }
116     return 0;
117 }