「BZOJ3545」[ONTAK2010]Peaks

Description

在Bytemountains有NN座山峰,每座山峰有他的高度hih_i。有些山峰之间有双向道路相连,共MM条路径,每条路径有一个困难值,这个值越大表示越难走,现在有QQ组询问,每组询问询问从点vv开始只经过困难值小于等于xx的路径所能到达的山峰中第kk高的山峰,如果无解输出1-1

Input

第一行三个数NNMMQQ
第二行NN个数,第ii个数为hih_i
接下来MM行,每行33个数a b c,表示从a到b有一条困难值为cc的双向路径。
接下来QQ行,每行三个数v x k,表示一组询问。

Output

对于每组询问,输出一个整数表示答案。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
10 11 4
1 2 3 4 5 6 7 8 9 10
1 4 4
2 5 3
9 8 2
7 8 10
7 1 4
6 7 1
6 4 8
2 1 5
10 8 10
3 4 7
3 4 6
1 5 2
1 5 6
1 5 8
8 9 2

Sample Output

1
2
3
4
6
1
-1
8

HINT

N105,M,Q5×105,hi,c,x109N\leq 10^5, M,Q\leq 5\times 10^5,h_i,c,x\leq 10^9

Solution

日常套路,对询问按照xx从小到大排序,对边按照ww从小到大排序,扫过去,然后线段树合并一波就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 1e5 + 666, M = 6e5 + 6;
int n, m, Q;
int h[N];
struct Edge {
int u, v, w;
}e[M];
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
struct Que {
int v, x, k, i;
}q[M];
bool cmpq(Que a, Que b) {
return a.x < b.x;
}
int ans[M], fa[N];
int getf(int x) {
return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
int rt[N];
struct T {
int l, r, c;
}t[N * 32];
int merge(int x, int y) {
if(!(x && y)) return x|y;
t[x].c += t[y].c;
t[x].l = merge(t[x].l, t[y].l);
t[x].r = merge(t[x].r, t[y].r);
return x;
}
void HB(int x, int y) {
int u = getf(x), v = getf(y);
if(u == v) return;
fa[u] = v;
rt[v] = merge(rt[u], rt[v]);
}
int tot;
void build(int &o, int l, int r, int x) {
o = ++tot;
t[o].c = 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) build(t[o].l, l, mid, x);
else build(t[o].r, mid + 1, r, x);
}
int query(int o, int x, int l, int r) {
if(t[o].c < x) return -1;
if(l == r) return l;
int val = t[o].c - t[t[o].l].c;
int mid = (l + r) >>1;
if(x <= val) return query(t[o].r, x, mid + 1, r);
else query(t[o].l, x - val, l, mid);
}
int main() {
n = read(), m = read(), Q = read();
for(int i = 1; i <= n; ++i) h[i] = read(), build(rt[i], 1, 1e9, h[i]);
for(int i = 1; i <= m; ++i) {
e[i].u = read(), e[i].v = read(), e[i].w = read();
}
sort(e + 1, e + 1 + m, cmp);
for(int i = 1; i <= Q; ++i) {
q[i].v = read(), q[i].x = read(), q[i].k = read();
q[i].i = i;
}
sort(q + 1, q +1 + Q, cmpq);
int p = 1;
for(int i = 1; i <= n; ++i) fa[i] = i;
for(int i = 1; i <= Q; ++i) {
while(p <= m && e[p].w <= q[i].x) HB(e[p].u, e[p].v), ++p;
ans[q[i].i] = query(rt[getf(q[i].v)], q[i].k, 1, 1e9);
}
for(int i = 1; i <= Q; ++i) writeln(ans[i]);
return 0;
}
`

BZOJ3551


建立kruskal重构树。其满足以下性质:

  1. 二叉树(好吧这题意义不大)
  2. 原树与新树两点间路径上边权(点权)的最大值相等
  3. 子节点的边权小于等于父亲节点(大根堆)
  4. 原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权

倍增找到最后一个vyxv_y\ge xyy,在其权值线段树下找第kk大的数。注意k=0k=0的时候,输出hih_i的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2e5 + 666;
int n, m, Q;
int a[N];
struct Edge {
int u, v, w;
}e[N * 3];
bool cmp(Edge a, Edge b) {
return a.w < b.w;
}
int fa[N];
int getf(int x) {
return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
int tot;
int v[N];
struct G {
struct Edge {
int u, v, nxt;
}e[N * 2];
int head[N], en;
void addedge(int x, int y) {
e[++en].u = x, e[en].v = y, e[en].nxt = head[x], head[x] = en;
e[++en].u = y, e[en].v = x, e[en].nxt = head[y], head[y] = en;
}
bool vis[N];
int f[N][19], rt[N], num;
struct Tree {
int l, r, c;
}t[N*30];
void build(int &o, int l, int r, int x) {
o = ++num;
t[o].c = 1;
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) build(t[o].l, l, mid, x);
else build(t[o].r, mid + 1, r, x);
}
int merge(int x, int y) {
if(!(x && y)) return x|y;
int o = ++num;
t[o].c = t[x].c + t[y].c;
t[o].l = merge(t[x].l, t[y].l);
t[o].r = merge(t[x].r, t[y].r); //尽量不要直接合并
return o;
/* t[x].c = t[x].c + t[y].c;
t[x].l = merge(t[x].l, t[y].l);
t[x].r = merge(t[x].r, t[y].r);
return x;*/
}
void dfs(int x, int F) {
vis[x] = 1;
f[x][0] = F;
for(int i =1; i <= 18; ++i) f[x][i] = f[f[x][i - 1]][i - 1];
if(x <= n) {
build(rt[x], 1, 1e9, a[x]);
} else rt[x] = ++num;
for(int i = head[x]; i;i = e[i].nxt) {
int y = e[i].v;
if(y == F) continue;
dfs(y, x);
rt[x] = merge(rt[x], rt[y]); //不能直接赋值,像这样合并可能就直接rt[x]=rt[y]直接出错
}
}
void init() {
for(int i = tot; i; --i) if(!vis[i]) dfs(i, i);
}
int get(int x, int val) {
for(int i = 18;~i;--i)
if(val >= v[f[x][i]]) x = f[x][i];
return x;
}
int query(int o, int l, int r, int x) {
if(t[o].c < x) return -1;
if(l == r) return l;
int mid = (l + r) >> 1;
int val = t[t[o].r].c ;
if(val >= x) return query(t[o].r, mid + 1, r, x);
else return query(t[o].l, l, mid, x - val);
}
}g;
int main() {
int mx = 0;
n = read(), m = read(), Q = read();
for(int i = 1; i <= n; ++i) a[i] = read(), fa[i] = i, mx = max(mx, a[i]);
for(int i = 1; i <= m; ++i) {
e[i].u = read(), e[i].v = read(), e[i].w = read();
}
sort(e + 1, e + 1 + m, cmp);
tot = n;
for(int i = 1; i <= m; ++i) {
int x = getf(e[i].u), y = getf(e[i].v);
if(x == y) continue;
++tot;
g.addedge(x, tot);
g.addedge(y, tot);
v[tot] = e[i].w;
fa[x] = tot;
fa[y] = tot;
fa[tot] = tot;
}
g.init();
int ans = 0;
while(Q--) {
int v = read(), x = read(), k = read();
v ^= ans;
x ^= ans;
k ^= ans;

int y = g.get(v, x);
if(k == 0) writeln(ans = mx);
else
writeln(ans = g.query(g.rt[y], 1, 1e9, k));
if(ans == -1) ans = 0;
}
return 0;
}