Description
在Bytemountains有座山峰，每座山峰有他的高度
。有些山峰之间有双向道路相连，共
条路径，每条路径有一个困难值，这个值越大表示越难走，现在有
组询问，每组询问询问从点
开始只经过困难值小于等于
的路径所能到达的山峰中第
高的山峰，如果无解输出
。
Input
第一行三个数，
，
。
第二行个数，第
个数为
接下来行，每行
个数
a b c，表示从a到b有一条困难值为的双向路径。
接下来行，每行三个数
v x k，表示一组询问。
Output
对于每组询问，输出一个整数表示答案。
Sample Input
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
6 1 -1 8
HINT
。
Solution
日常套路，对询问按照从小到大排序，对边按照
从小到大排序，扫过去，然后线段树合并一波就行了。
#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重构树。其满足以下性质：
- 二叉树(好吧这题意义不大)
- 原树与新树两点间路径上边权(点权)的最大值相等
- 子节点的边权小于等于父亲节点(大根堆)
- 原树中两点之间路径上边权的最大值等于新树上两点的LCA的点权
倍增找到最后一个的
，在其权值线段树下找第
大的数。注意
的时候，输出
的最大值。
#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;
}
京公网安备 11010502036488号