「bzoj3551」Peaks加强版 - Kruskal重构树+主席树 | Bill Yang's Blog
0%

「bzoj3551」Peaks加强版 - Kruskal重构树+主席树

题目大意

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


题目分析

不能离线处理询问了,那么我们就不能保证图中$x$的限制。
考虑若要沿着一条路径走到另一个点,会使用怎样的路径?一定沿着最小生成树上的边走
那么现在我们转化为了快速求最小生成树上小于等于$x$的边集。
不难想到Kruskal重构树。

建立Kruskal重构树,因为Kruskal重构树满足大根堆的性质,因此从点$v$向上爬树一直爬到不符合条件的点$y$时($Val[y]\le x,Val[fa[y]]\gt x$),$y$所在的子树即为可以选择的边集。
现在解决了$x$的限制,如何求出范围中的第$k$大呢?
搞出Dfs序,主席树查询$k$大即可。

注意本题指针很乱,容易写错。


代码

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
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=100005;

struct President_Tree {
struct Tree {
int ls,rs,size;
} tree[maxn*50];
int size;
int insert(int left,int right,int pre,int val) {
int now=++size;
tree[now]=tree[pre];
tree[now].size++;
if(left==right)return now;
int mid=(left+right)>>1;
if(val<=mid)tree[now].ls=insert(left,mid,tree[pre].ls,val);
else tree[now].rs=insert(mid+1,right,tree[pre].rs,val);
return now;
}
int query(int left,int right,int lt,int rt,int rank) {
if(left==right)return left;
int mid=(left+right)>>1,sum=tree[tree[rt].rs].size-tree[tree[lt].rs].size;
if(rank<=sum)return query(mid+1,right,tree[lt].rs,tree[rt].rs,rank);
else return query(left,mid,tree[lt].ls,tree[rt].ls,rank-sum);
}
} pt;

struct Edge {
int from,to,dist;
Edge(int x,int y,int v):from(x),to(y),dist(v) {}
bool operator < (const Edge& b) const {
return dist<b.dist;
}
};

struct tmp {
int v,id;
bool operator < (const tmp& b) const {
return v<b.v;
}
} b[maxn*2];

vector<Edge> edges;
int n,m,q,cnt,step,lastans,fM[maxn],root[maxn],a[maxn*2],father[maxn*2],p[maxn*2][25],Dfn[maxn*2],First[maxn*2],Last[maxn*2],lson[maxn*2],rson[maxn*2];
bool vst[maxn*2];

int Get_Father(int x) {
if(father[x]==x)return x;
return father[x]=Get_Father(father[x]);
}

void Sparse_Table() {
for(int j=1; j<20; j++)
for(int i=1; i<=cnt; i++)
if(~p[i][j-1])p[i][j]=p[p[i][j-1]][j-1];
}

void Dfs(int Now) {
vst[Now]=1;
if(Now<=n)Dfn[++step]=Now;
First[Now]=step;
if(lson[Now])Dfs(lson[Now]);
if(rson[Now])Dfs(rson[Now]);
Last[Now]=step;
}

int main() {
cnt=n=Get_Int();
m=Get_Int();
q=Get_Int();
for(int i=1; i<=n; i++)a[i]=Get_Int();
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
edges.push_back(Edge(x,y,v));
}
sort(edges.begin(),edges.end());
for(int i=1; i<=2*n; i++)father[i]=i;
memset(p,-1,sizeof(p));
for(auto e:edges) {
int fx=Get_Father(e.from),fy=Get_Father(e.to);
if(fx!=fy) {
p[fx][0]=p[fy][0]=father[fx]=father[fy]=++cnt;
lson[cnt]=fx,rson[cnt]=fy;
a[cnt]=e.dist;
}
}
Sparse_Table();
for(int i=1; i<=n; i++) {
b[i].v=a[i];
b[i].id=i;
}
sort(b+1,b+n+1);
for(int i=1; i<=n; i++) { //离散化
fM[i]=a[b[i].id];
a[b[i].id]=i;
}
for(int i=cnt; i>=1; i--)
if(!vst[i])Dfs(i);
for(int i=1; i<=n; i++)root[i]=pt.insert(1,n,root[i-1],a[Dfn[i]]);
while(q--) {
if(lastans==-1)lastans=0;
int x=Get_Int()^lastans,y=Get_Int()^lastans,k=Get_Int()^lastans;
for(int i=19; i>=0; i--)
if(~p[x][i]&&a[p[x][i]]<=y)x=p[x][i];
int l=First[x]+1,r=Last[x];
if(pt.tree[root[r]].size-pt.tree[root[l-1]].size<k)lastans=-1;
else lastans=fM[pt.query(1,n,root[l-1],root[r],k)];
printf("%d\n",lastans);
}
return 0;
}
姥爷们赏瓶冰阔落吧~