洛谷 P4197&&P7834 Peaks 题解

算法分析

这道题分成两部分$:1.$区间第 $k$ 大，需要用到主席树。$2.Kruskal$ 重构树。

区间第 $k$ 大的话，套一个主席树模板即可，注意求的是第 $k$ 大，不是第 $k$ 小，本人犯了低级错误，被队友一秒钟指出。

自己写的关于 $Kruskal$ 重构树的博客，欢迎来看

然后来看如何构建 $Kruskal$ 重构树。我们按照山峰的高度从小到大排序，然后构建重构树。由于我们需要从 $v$ 点开始只经过困难值小于等于 $x$ 的路径能到达的山峰中的第 $k$ 高峰，所以我们可以倍增去找到一个点 $u$，满足 $val[u]\le x$ 并且 $val[fa[u]]>x$。

我们需要在构建完重构树之后，进行一次 $dfs$，预处理出倍增数组和该点的子树所对应的 $dfn$ 区间。

对于每一次询问，我们先找到上述的点 $u$，然后在 $u$ 对应的子树中通过主席树求出区间第 $k$ 大。

如何判无解呢？我们在 $dfs$ 的过程中，记录下来每一个点对应的子树中，有多少个叶子节点，记为 $siz[u]$。因为叶子节点就是原树中的节点。如果 $siz[u]<k$，说明该区间一共都没有 $k$ 个数，自然是无解的。

注意本题 $h[i]\le 10^9$，需要离散化。

#include 
#include 
#include 
#include 
#include 
#define re register
#define drep(a,b,c) for(re int a(b) ; a>=(c) ; --a)
#define rep(a,b,c) 	for(re int a(b) ; a<=(c) ; ++a)
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch == '-') f=-1 ; ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
inline void print(int x){
	if(x < 0) putchar('-'),x = -x;
	if(x >= 10) print(x / 10);
	putchar(x % 10 + '0');
}
const int M = 4e6+10;
const int N = 5e5+10;
int n,m,q,cnt,idx,tot,num,segcnt,last;
int head[N],h[N],lsh[N],f[N][25];
int fa[N],pos[N],st[N],ed[N],val[N],siz[N];
struct node{
	int x,y,hard;
	friend bool operator < (node a,node b) { return a.hard < b.hard;}
}a[N];
struct edge{
	int to,nxt;
}e[N];
inline void add(int u,int v){
	e[++cnt].to = v;
	e[cnt].nxt = head[u];
	head[u] = cnt;
}
inline int find(int x){
	if(fa[x] == x) return x;
	return fa[x] = find(fa[x]);
}
inline void dfs(int u,int pa){
	f[u][0] = pa,pos[++num] = u,st[u] = num;
	rep(i,1,20) f[u][i] = f[f[u][i-1]][i-1];
	for(re int i(head[u]) ; i ; i=e[i].nxt){
		int v = e[i].to;
		if(v == pa) continue;
		dfs(v,u);
		siz[u] += siz[v];
	}
	if(!siz[u]) siz[u] = 1;
	ed[u] = num;
}
inline void rebuild(){
	idx = n;
	sort(a+1,a+m+1);
	rep(i,1,n<<1) fa[i] = i;
	rep(i,1,m){
		int x = a[i].x,y = a[i].y;
		int fx = find(x),fy = find(y);
		if(fx == fy) continue;
		fa[fx] = fa[fy] = ++idx;
		val[idx] = a[i].hard;
		add(idx,fx),add(idx,fy);
		if(idx == (n<<1)-1) break;
	}
	dfs(idx,0);
}
int root[N];
struct tree{
	int ls,rs,v;
}t[N<<5];
inline void build(int &rt,int l,int r){
	rt = ++segcnt;
	if(l == r) return;
	int mid = (l+r)>>1;
	build(t[rt].ls,l,mid);
	build(t[rt].rs,mid+1,r);
}
inline int modify(int rt,int l,int r,int x){
	int node = ++segcnt;
	t[node] = t[rt];
	t[node].v = t[rt].v+1;
	if(l == r) return node;
	int mid = (l+r)>>1;
	if(x <= mid) t[node].ls = modify(t[rt].ls,l,mid,x);
	else t[node].rs = modify(t[rt].rs,mid+1,r,x);
	return node;
}
inline int query(int x,int y,int l,int r,int kth){
	int delta = t[t[y].rs].v - t[t[x].rs].v;
	if(l == r) return l;
	int mid = (l+r)>>1;
	if(kth > delta) return query(t[x].ls,t[y].ls,l,mid,kth-delta);
	else return query(t[x].rs,t[y].rs,mid+1,r,kth);
}
signed main(){
	n = read(),m = read(),q = read();
	rep(i,1,n) lsh[i] = h[i] = read();
	sort(lsh+1,lsh+n+1);
	tot = unique(lsh+1,lsh+n+1)-lsh-1;
	rep(i,1,n) h[i] = lower_bound(lsh+1,lsh+tot+1,h[i])-lsh;
	rep(i,1,m) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].hard);
	rebuild();
	rep(i,1,idx){
		root[i] = root[i-1];
		if(pos[i] <= n) root[i] = modify(root[i-1],1,tot,h[pos[i]]);
	}
	while(q--){
		int v = read(),x = read(),k = read();
		drep(i,20,0) if(f[v][i] && val[f[v][i]]<=x) v = f[v][i];
		if(siz[v] < k){
			printf("-1\n");
			continue;
		}
		printf("%d\n",last = lsh[query(root[st[v]-1],root[ed[v]],1,tot,k)]);
	}
	return 0;
}
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