题目大意
在Bytemountains有$N$座山峰，每座山峰有它的高度$h_i$。有些山峰之间有双向道路相连，共$M$条路径，每条路径有一个困难值，这个值越大表示越难走，现在有$Q$组询问，每组询问询问从点$v$开始只经过困难值小于等于$x$的路径所能到达的山峰中第$k$高的山峰，如果无解输出$-1$。
题目分析
不妨将询问离线下来，对$x$从小到大排序，每次仅插入边权小于等于$x$的边。
因此在回答每个询问时，图中的边均小于等于$x$。
接下来我们需要考虑所有可达点的$k$大。
不妨使用启发式合并Splay维护连通块，因此可以完成合并、查询$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
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
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=200005;
struct Tree {
int father,child[2]; //0左儿子 1右儿子
int key,size; //key为结点属性 size为子树大小
Tree() {}
Tree(int fa,int lc,int rc,int data,int sz):father(fa),key(data),size(sz) {
child[0]=lc,child[1]=rc;
}
};
struct Splay {
int father[maxn];
Tree tree[maxn];
void init(int n) {
memset(tree,0,sizeof(tree));
for(int i=1; i<=n; i++)father[i]=i;
}
void clear(int index) {
tree[index]=Tree(0,0,0,0,0);
}
int checkson(int index) { //判断是父亲的左儿子还是右儿子
return tree[tree[index].father].child[1]==index;
}
void update(int index) { //更新size
if(!index)return;
tree[index].size=1;
if(tree[index].child[0])tree[index].size+=tree[tree[index].child[0]].size;
if(tree[index].child[1])tree[index].size+=tree[tree[index].child[1]].size;
}
void rotate(int index) { //旋转到根
int father=tree[index].father,grandpa=tree[father].father,side=checkson(index);
tree[father].child[side]=tree[index].child[side^1];
tree[tree[father].child[side]].father=father;
tree[father].father=index;
tree[index].child[side^1]=father;
tree[index].father=grandpa;
if(grandpa)tree[grandpa].child[tree[grandpa].child[1]==father]=index;
update(father);
update(index);
}
void splay(int index,int root) {
if(index==root)return;
for(int father; (father=tree[index].father); rotate(index)) //基本旋转
if(tree[father].father)rotate((checkson(index)==checkson(father))?father:index); //附加旋转
root=index;
}
void splay(int index) {
int root=get_root(index);
splay(index,root);
}
void insertnew(int index,int v) { //插入没有的结点
tree[index]=Tree(0,0,0,v,1);
}
void insert(int index,int root) { //插入已有结点
splay(root);
int now=root,father=0,v=tree[index].key;
while(true) {
father=now; //保存父亲
now=tree[now].child[tree[now].key<v]; //往哪边走
if(!now) {
tree[index]=Tree(father,0,0,v,1);
tree[father].child[tree[father].key<v]=index;
update(father);
splay(index,root);
break;
}
}
}
int find(int rank,int root) { //找到排名为rank的点，返回下标
int now=root;
while(true) {
if(rank<=0||now<=0)return -1; //找不到
if(tree[now].child[0]&&rank<=tree[tree[now].child[0]].size)now=tree[now].child[0];
else {
int tmp=(tree[now].child[0]?tree[tree[now].child[0]].size:0)+1;
if(rank<=tmp)return now;
rank-=tmp;
now=tree[now].child[1];
}
}
}
int get_root(int x) {
if(tree[x].father==0)return x;
else return get_root(tree[x].father);
}
int Get_Father(int x) {
if(father[x]==x)return x;
else return father[x]=Get_Father(father[x]);
}
void Dfs(int x,int y) {
if(tree[x].child[0])Dfs(tree[x].child[0],y);
if(tree[x].child[1])Dfs(tree[x].child[1],y);
tree[x].father=tree[x].child[0]=tree[x].child[1]=tree[x].size=0;
insert(x,y);
}
void link(int x,int y) {
int f1=Get_Father(x),f2=Get_Father(y);
if(f1==f2)return; //已经合并
father[f1]=f2;
splay(x);
splay(y);
if(tree[x].size>tree[y].size)Dfs(y,x);
else Dfs(x,y);
}
} bbt;
struct Edge {
int from,to,dist;
bool operator < (const Edge& b) const {
return dist<b.dist;
}
} edges[1000005];
struct Question {
int st,limit,k;
int id,ans;
bool operator < (const Question& b) const {
return limit<b.limit;
}
} question[1000005];
bool cmp(Question a,Question b) {
return a.id<b.id;
}
int n,m,q;
int main() {
n=Get_Int();
m=Get_Int();
q=Get_Int();
bbt.init(n);
for(int i=1; i<=n; i++)bbt.insertnew(i,Get_Int());
for(int i=1; i<=m; i++) {
edges[i].from=Get_Int();
edges[i].to=Get_Int();
edges[i].dist=Get_Int();
}
sort(edges+1,edges+m+1);
for(int i=1; i<=q; i++) {
question[i].st=Get_Int();
question[i].limit=Get_Int();
question[i].k=Get_Int();
question[i].id=i;
}
sort(question+1,question+q+1);
int j=1;
for(int i=1; i<=q; i++) {
for(; j<=m; j++) {
if(edges[j].dist>question[i].limit)break;
bbt.link(edges[j].from,edges[j].to);
}
bbt.splay(question[i].st);
question[i].ans=bbt.find(bbt.tree[question[i].st].size-question[i].k+1,question[i].st);
}
sort(question+1,question+q+1,cmp);
for(int i=1; i<=q; i++)
if(question[i].ans==-1)puts("-1");
else printf("%d\n",bbt.tree[question[i].ans].key);
return 0;
}
