OI - Peaks加强版(BZOJ)

学了 Kruskal 重构树,打了版题就来撸这道题……

(学习笔记还没写)


Part1. 题面

(emm…原题是BZOJ的权限题,但是…… ☻)

有 n 座山峰,有 m 条双向山路连接两座山峰。第 i 座山峰的高度为 $h_i$。第 i 条山路连接山峰 $a_i$ 和 $b_i$,它的危险参数为 $d_i$。

现在有 q 个人想要去登山。第 i 个人从山峰 $s_i$ 出发,他不敢走危险度大于(严格)$x_i$ 的山路,他想知道他能登上的第 $k_i$ 高(即从大到小第 $k_i$ 座)的山峰的高度是多少。

给出每座山峰的高度 $h_i$、每条山路的 $a_i,b_i,d_i$ 和每个人的 $s_i,x_i,k_i$。对于每一个人,回答他能登上的第 $k_i$ 高的山峰的高度,如果他能登上的山峰数量小于 $k_i$,输出 -1。

强制在线。

数据规模:$1\le n\le10^5$;$m,q\le5\times10^5$;$h_i,x_i,d_i\le10^9$


Part2. 解析

Kruskal 重构树有一些有意思的性质,比如这道题用到的:

  • 它是一个大根堆(如果是最小生成树);
  • 任意两点 u,v 在原图上“最大边最小”的路径上的最大边是重构树上 u,v 的 LCA

只要理解到这两点,就可以理清题解的思想了。因为如果第 i 个人能从 u 到 v,那么 u 到 v 的“最大边最小”的路径的最大边不能超过 $x_i$。

因此只要找到重构树中 $s_i$ 的最浅的、小于等于 $x_i$ 的祖先 pre。又因为重构树是大根堆,pre 的子树中一定都比 pre 本身小,也就是说第 i 个人只能在 pre 的子树中走。那么现在问题来了——怎么找 pre?

—— 倍增!对!先求出每个点的第 $2^i$ 个祖先,然后倍增往上爬!

怎么判断这个当前点到它的祖先的路径上没有比 $x_i$ 大的节点?再倍增维护一个从当前节点到它的第 $2^i$ 个祖先的路径上的最大点?

—— 然而这样你就 MLE 了!再一次利用到大根堆性质,如果该祖先的权值小于等于 $x_i$,那么当前点到该祖先的路径上的权值一定都不超过 $x_i$,所以只要判断祖先的点权是不是不超过 $x_i$ 就行了。

然后现在就留下这样一个问题:求在某一个子树内的第 k 高的山。

求第 k 大?好像比较常用的就是主席树和平衡树了。这里又是在子树内询问,对于一棵子树,我们知道它的 dfn 是连续的,所以可以转换为求一个线段!然后就主席树了。


Part3. 源代码

竟然不算特别长……

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
/*Lucky_Glass*/
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5,M=5e5,MN=M+N+3;

int n,m,q,cntn,dfnn;
int hgt[N+3],id[N+3];
int dif[MN],ch[MN][2];
int pre[MN][21];
int dfn[N+3],bet[MN][2];
vector<int> uni;

struct DSU{
int fa[N+3],Top[N+3];
void Init(){
for(int i=1;i<=n;i++){
fa[i]=Top[i]=i;
dif[i]=0;
}
}
int FindFa(int u){
if(u==fa[u]) return u;
return fa[u]=FindFa(fa[u]);
}
bool Merge(int u,int v,int wgt){
int fu=FindFa(u),fv=FindFa(v);
if(fu==fv) return false;
++cntn;
dif[cntn]=wgt;
ch[cntn][0]=Top[fu];ch[cntn][1]=Top[fv];
Top[fv]=cntn;
fa[fu]=fv;
return true;
}
}D;
struct EDGE{int u,v,dif;}edg[M+3];
struct SNODE{
int siz;
SNODE *ch[2];
};
struct SEGTREE{
SNODE pol[N*20],*Scnt,*NIL,*root[N+3];
SEGTREE(){
NIL=Scnt=pol;
NIL->ch[0]=NIL->ch[1]=NIL;
NIL->siz=0;
fill(root,root+N+1,NIL);
}
SNODE *NewNode(){
SNODE *p=++Scnt;
*p=*NIL;
return p;
}
void Modify(SNODE *&now,SNODE *pst,int Cl,int Cr,int num){
if(now==NIL) now=NewNode();
*now=*pst;now->siz++;
if(Cl==Cr) return;
int Cm=(Cl+Cr)>>1;
if(num<=Cm){
now->ch[0]=NIL;
Modify(now->ch[0],pst->ch[0],Cl,Cm,num);
}
else{
now->ch[1]=NIL;
Modify(now->ch[1],pst->ch[1],Cm+1,Cr,num);
}
}
int Query(SNODE *now,SNODE *pst,int Cl,int Cr,int rnk){
if(Cl==Cr) return Cl;
int Cm=(Cl+Cr)>>1;
int siz=now->ch[1]->siz - pst->ch[1]->siz;
if(siz>=rnk)
return Query(now->ch[1],pst->ch[1],Cm+1,Cr,rnk);
else
return Query(now->ch[0],pst->ch[0],Cl,Cm,rnk-siz);
}
SNODE*& operator [](int id){
return root[id];
}
}S;

void DFS(int u,int fa){
pre[u][0]=fa;
for(int i=1;i<21;i++)
pre[u][i]=pre[pre[u][i-1]][i-1];
if(u<=n){
bet[u][0]=bet[u][1]=dfn[u]=++dfnn;
return;
}
bet[u][0]=bet[u][1]=dfnn+1;
DFS(ch[u][0],u);DFS(ch[u][1],u);
bet[u][1]=bet[ch[u][1]][1];
}
int RchMax(int u,int lim){
dif[0]=1e9+3;
for(int i=20;i>=0;i--)
if(dif[pre[u][i]]<=lim)
u=pre[u][i];
return u;
}
bool cmpEDGE(const EDGE &A,const EDGE &B){return A.dif<B.dif;}
bool cmpID(const int &A,const int &B){return dfn[A]<dfn[B];}
int main(){
scanf("%d%d%d",&n,&m,&q);
cntn=n;D.Init();
for(int i=1;i<=n;i++){
scanf("%d",&hgt[i]);
uni.push_back(hgt[i]);
}
for(int i=1;i<=m;i++)
scanf("%d%d%d",&edg[i].u,&edg[i].v,&edg[i].dif);
sort(edg+1,edg+1+m,cmpEDGE);
sort(uni.begin(),uni.end());
uni.erase(unique(uni.begin(),uni.end()),uni.end());
for(int i=1;i<=m;i++) D.Merge(edg[i].u,edg[i].v,edg[i].dif);
for(int i=1;i<=n;i++) hgt[i]=lower_bound(uni.begin(),uni.end(),hgt[i])-uni.begin()+1;
for(int i=cntn;i>=0;i--)
if(!bet[i][0])
DFS(i,0);
for(int i=1;i<=n;i++) id[i]=i;
sort(id+1,id+1+n,cmpID);
for(int i=1;i<=n;i++)
S.Modify(S[i],S[i-1],1,uni.size(),hgt[id[i]]);
int las=-1;
while(q--){
int u,lim,rnk;scanf("%d%d%d",&u,&lim,&rnk);
int Top=RchMax(u,lim),rig=bet[Top][1],lef=bet[Top][0]-1;
if(S[rig]->siz-S[lef]->siz<rnk) printf("%d\n",las=-1);
else printf("%d\n",las=uni[S.Query(S[rig],S[lef],1,uni.size(),rnk)-1]);
}
return 0;
}

The End

Thanks for reading!

还有两周就 CSP2019 了呢?竟然没什么紧张感诶……

0%