按照困难度升序排序
Kruskal重构树这样一来一个点的子树中的所有困难值都小于改点的困难值对于每次询问倍增找出困难值最大且小于x的点该点的子树中的第k大就是询问的答案主席书维护区间k大#include#include #include #include #include using namespace std;const int N = 1e5 + 10, M = 2e5 + 10;int n, m, Q;int A[N << 1], high[N << 1], val[N << 1];struct Node { int u, v, hard;} Edge[M * 10];struct Node_ { int v, nxt;} G[M * 10];int fa[N << 1];int Root[N << 1];int W[M * 10];int head[N << 1];int Lson[M * 10], Rson[M * 10];int now;int tree[N << 1], bef[N << 1], lst[N << 1], rst[N << 1], Tree;int N_;int f[N << 1][30];int Ans;int Segjs;int impjs;#define gc getchar()inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc; while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}inline bool Cmp(Node a, Node b) { return a.hard < b.hard;}int Get(int x) { return fa[x] == x ? x : fa[x] = Get(fa[x]);}inline void Add(int u, int v) { G[++ now].v = v; G[now].nxt = head[u]; head[u] = now;}inline void Pre() { for(int i = 1; i <= 20; i ++) for(int j = 1; j <= n * 2 - 1; j ++) f[j][i] = f[f[j][i - 1]][i - 1];}inline void Fill(int x, int y) { Lson[x] = Lson[y], Rson[x] = Rson[y], W[x] = W[y];}inline int Imp_find(int u, int x) { for(int i = 20; i >= 0; i --) if(f[u][i] && val[f[u][i]] <= x) u = f[u][i]; return u;}inline void Kruskal() { sort(Edge + 1, Edge + m + 1, Cmp); impjs = n; for(int i = 1; i <= n * 2; i ++) fa[i] = i; for(int i = 1; i <= n * 2; i ++) head[i] = -1; for(int i = 1; i <= m; i ++) { int fau = Get(Edge[i].u), fav = Get(Edge[i].v); if(fau != fav) { impjs ++; val[impjs] = Edge[i].hard; fa[fau] = fa[fav] = impjs; Add(impjs, fau), Add(fau, impjs), Add(impjs, fav), Add(fav, impjs); } if(impjs == n * 2 - 1) break; }}void Dfs(int u, int fa) { if(u <= n) { lst[u] = rst[u] = ++ Tree; bef[Tree] = u; } else lst[u] = n; for(int i = head[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(v == fa) continue; f[v][0] = u; Dfs(v, u); rst[u] = max(rst[u], rst[v]), lst[u] = min(lst[u], lst[v]); }}void Insert(int &rt, int l, int r, int x) { Fill(++ Segjs, rt); rt = Segjs; W[rt] ++; if(l == r) return ; int mid = (l + r) >> 1; if(x <= mid) Insert(Lson[rt], l, mid, x); else Insert(Rson[rt], mid + 1, r, x);}void Sec_A(int jd1, int jd2, int l, int r, int k) { if(l == r) {Ans = l; return ;} if(W[jd2] - W[jd1] < k) {Ans = -1; return ;} int mid = (l + r) >> 1; if(W[Rson[jd2]] - W[Rson[jd1]] >= k) Sec_A(Rson[jd1], Rson[jd2], mid + 1, r, k); else Sec_A(Lson[jd1], Lson[jd2], l, mid, k - (W[Rson[jd2]] - W[Rson[jd1]]));}int main() { n = read(), m = read(), Q = read(); for(int i = 1; i <= n; i ++) A[i] = read(), high[i] = A[i]; for(int i = 1; i <= m; i ++) { int a = read(), b = read(), c = read(); Edge[i] = (Node) {a, b, c}; } sort(A + 1, A + n + 1); int a = unique(A + 1, A + n + 1) - A - 1; for(int i = 1; i <= n; i ++) high[i] = lower_bound(A + 1, A + a + 1, high[i]) - A; Kruskal(); Dfs(impjs, 0); Pre(); for(int i = 1; i <= n; i ++) { Root[i] = Root[i - 1]; Insert(Root[i], 1, n, high[bef[i]]); } for(; Q; Q --) { int v = read(), x = read(), k = read(); if(Ans != -1) v ^= Ans, x ^= Ans, k ^= Ans; int use = Imp_find(v, x); Sec_A(Root[lst[use] - 1], Root[rst[use]], 1, n, k); if(Ans != -1) Ans = A[Ans]; printf("%d\n", Ans); } return 0;}