小型网站的建设方案,网络营销策略概念,wordpress 缓存查询,软件开发的几个阶段#3551. [ONTAK2010]Peaks加强版
我们要求从一个点出发经过困难值小于等于xxx的路径所能到达的山峰中第kkk高的是什么。
考虑按照边权升序#xff0c;建议kruskalkruskalkruskal重构树#xff0c;然后倍增向上跳#xff0c;找到困难值小于等于xxx的深度最小的节点uuu#…#3551. [ONTAK2010]Peaks加强版
我们要求从一个点出发经过困难值小于等于xxx的路径所能到达的山峰中第kkk高的是什么。
考虑按照边权升序建议kruskalkruskalkruskal重构树然后倍增向上跳找到困难值小于等于xxx的深度最小的节点uuu
那么我们只要在uuu的子树中询问第kkk大即可所以可以用主席树来写依照dfsdfsdfs序对每个节点建立一颗主席树然后在主席树上查找第kkk大即可。
#include bits/stdc.husing namespace std;const int N 5e5 10;int head[N], to[N], nex[N], cnt 1;int n, m, q, nn, a[N], ff[N], value[N], h[N];int fa[N][21], l[N], r[N], rk[N], tot;int root[N], ls[N 7], rs[N 7], sum[N 7], num;struct Res {int u, v, w;bool operator (const Res t) const {return w t.w;}
}edge[N];void add(int x, int y) {to[cnt] y;nex[cnt] head[x];head[x] cnt;
}void update(int rt, int pre, int l, int r, int x, int v) {rt num;ls[rt] ls[pre], rs[rt] rs[pre], sum[rt] sum[pre] v;if (l r) {return ;}int mid l r 1;if (x mid) {update(ls[rt], ls[pre], l, mid, x, v);}else {update(rs[rt], rs[pre], mid 1, r, x, v);}
}int query(int L, int R, int l, int r, int k) {if (l r) {return l;}int res sum[ls[R]] - sum[ls[L]], mid l r 1;if (res k) {return query(ls[L], ls[R], l, mid, k);}else {return query(rs[L], rs[R], mid 1, r, k - res);}
}int find(int rt) {return rt ff[rt] ? rt : ff[rt] find(ff[rt]);
}void dfs(int rt, int f) {fa[rt][0] f, l[rt] tot, rk[tot] rt;for (int i 1; i 20; i) {fa[rt][i] fa[fa[rt][i - 1]][i - 1];}for (int i head[rt]; i; i nex[i]) {if (to[i] f) {continue;}dfs(to[i], rt);}r[rt] tot;
}void kruskal() {for (int i 1; i N; i) {ff[i] i;}sort(edge 1, edge 1 m);for (int i 1, cur 1; i m cur n; i) {int u find(edge[i].u), v find(edge[i].v);if (u ! v) {cur, nn;ff[u] nn, ff[v] nn;value[nn] edge[i].w;add(nn, u), add(nn, v);if (u n) {value[u] edge[i].w;}if (v n) {value[v] edge[i].w;}}}dfs(nn, 0);
}int main() {// freopen(in.txt, r, stdin);// freopen(out.txt, w, stdout);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);scanf(%d %d %d, n, m, q);for (int i 1; i n; i) {scanf(%d, h[i]);a[i] h[i];}nn n;for (int i 1; i m; i) {scanf(%d %d %d, edge[i].u, edge[i].v, edge[i].w);}kruskal();int maxn n;sort(a 1, a 1 maxn);maxn unique(a 1, a 1 maxn) - (a 1);for (int i 1; i n; i) {h[i] lower_bound(a 1, a 1 maxn, h[i]) - a; }for (int i 1; i nn; i) {root[i] root[i - 1];if (rk[i] n) {update(root[i], root[i], 1, maxn, h[rk[i]], 1);}}for (int i 1, u, x, k, last_ans 0, res; i q; i) {scanf(%d %d %d, u, x, k);if (last_ans ! -1) {u ^ last_ans, x ^ last_ans, k ^ last_ans;}for (int j 20; j 0; j--) {if (fa[u][j] value[fa[u][j]] x) {u fa[u][j];}}res sum[root[r[u]]] - sum[root[l[u] - 1]];last_ans res k ? -1 : a[query(root[l[u] - 1], root[r[u]], 1, maxn, res - k 1)];printf(%d\n, last_ans);}return 0;
}
