【BZOJ3551】【BZOJ3545】 【ONTAK2010】 Peaks (kruskal重构树+主席树)

Description

​ 在\(Bytemountains\)有\(~n~\)座山峰,每座山峰有他的高度\(~h_i~\)。 有些山峰之间有双向道路相连,共\(~m~\)条路径,每条路径有一个困难值,这个值越大表示越难走,现在有\(~q~\)组询问,每组询问询问从点\(~v~\)开始只经过困难值小于等于\(~x~\)的路径所能到达的山峰中第\(~k~\)高的山峰,如果无解输出\(-1\)。强制在线。

Solution

​ 把边从小到大排序插入\(kruskal\)重构树中,对于每次询问, 倍增求出\(~v~\)祖先中第一个小于\(~x~\)的瓶颈,子树第\(~k~\)大用主席树维护即可,只不过主席树记的是第\(~k~\)小的值,记得要反过来查询。

Code

#include<bits/stdc++.h>
#define For(i, j, k) for(int i = j; i <= k; ++i)
#define Forr(i, j, k) for(int i = j; i >= k; --i)
#define Travel(i, u) for(int i = beg[u], v = to[i]; i; i = nex[i], v = to[i])
using namespace std; inline int read() {
int x = 0, p = 1; char c = getchar();
for(; !isdigit(c); c = getchar()) if(c == '-') p = -1;
for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x *= p;
} inline void File() {
#ifndef ONLINE_JUDGE
freopen("bzoj3545.in", "r", stdin);
freopen("bzoj3545.out", "w", stdout);
#endif
} const int N = 2e5 + 10, M = N << 2, MAXE = 5e5 + 10;
int n, m, q, st[N], ed[N], h[N], F[20][N], cnt, clk, ls[N], lstans;
int e = 1, beg[N], nex[M], to[M], fa[N], pos[N], rt[N], tot, hh[N], id[N];
struct edge { int u, v, w; } E[MAXE]; inline void add(int x, int y) { to[++ e] = y, nex[e] = beg[x], beg[x] = e; }
inline bool cmp(const edge &a, const edge &b) { return a.w < b.w; }
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
inline void dfs(int u, int f) { pos[st[u] = ++ clk] = u; Travel(i, u) dfs(v, u); ed[u] = clk; } inline void rebuild() {
For(i, 1, n << 1) fa[i] = id[i] = i;
For(i, 1, m) E[i].u = read(), E[i].v = read(), E[i].w = read();
sort(E + 1, E + 1 + m, cmp); For(i, 1, m) {
int u = E[i].u, v = E[i].v;
if (find(u) == find(v)) continue;
u = fa[u], v = fa[v], hh[++ cnt] = E[i].w;
add(cnt, u), add(cnt, v); fa[u] = fa[v] = cnt;
F[0][u] = F[0][v] = cnt;
}
F[0][cnt] = cnt; dfs(cnt, cnt);
} namespace Segment_Tree {
#define mid (l + r >> 1)
int c = 0; struct node { int lc, rc, v; } tr[N * 30]; inline void update(int &now, int pre, int l, int r, int rk) {
now = ++ c, tr[now] = tr[pre], ++ tr[now].v;
if (l < r) {
if (rk <= mid)
update(tr[now].lc, tr[pre].lc, l, mid, rk);
else
update(tr[now].rc, tr[pre].rc, mid + 1, r, rk);
}
} inline int query(int u, int v, int l, int r, int rk) {
if (l == r) return l;
int num = tr[tr[v].lc].v - tr[tr[u].lc].v;
if (rk <= num)
return query(tr[u].lc, tr[v].lc, l, mid, rk);
else
return query(tr[u].rc, tr[v].rc, mid + 1, r, rk - num);
} #undef mid
} using namespace Segment_Tree; inline void LS() {
sort(ls + 1, ls + 1 + n);
tot = unique(ls + 1, ls + 1 + n) - ls - 1;
For(i, 1, n) h[i] = lower_bound(ls + 1, ls + 1 + tot, h[i]) - ls; For(i, 1, cnt) {
if (pos[i] <= n)
update(rt[i], rt[i - 1], 1, tot, h[pos[i]]);
else
rt[i] = rt[i - 1];
}
For(j, 1, 18) For(i, 1, cnt) F[j][i] = F[j - 1][F[j - 1][i]];
} int main() {
File();
cnt = n = read(), m = read(), q = read();
For(i, 1, n) ls[i] = h[i] = read(); rebuild(), LS(); while (q --) {
int v = read(), x = read(), k = read();
if (lstans != -1) v ^= lstans, x ^= lstans, k ^= lstans;
Forr(i, 18, 0) if (hh[F[i][v]] <= x) v = F[i][v]; int res = tr[rt[ed[v]]].v - tr[rt[st[v] - 1]].v;
if (res < k) puts("-1"), lstans = -1;
else {
lstans = ls[query(rt[st[v] - 1], rt[ed[v]], 1, tot, res - k + 1)];
printf("%d\n" ,lstans);
}
}
return 0;
}
上一篇:Vue: 用 key 管理可复用的元素


下一篇:APPium-Xpath,swipe练习