【bzoj3545】[ONTAK2010]Peaks

2014年8月26日3,0352

Description

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

Input

第一行三个数N,M,Q。
第二行N个数,第i个数为h_i
接下来M行,每行3个数a b c,表示从a到b有一条困难值为c的双向路径。
接下来Q行,每行三个数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

【数据范围】
N<=10^5, M,Q<=5*10^5,h_i,c,x<=10^9。

题解

唉。。。

为啥我要作死的写线段树合并T T

谁告诉我这个复杂度是啥,为何比平衡树的启发式合并慢

做法就是离线后按照边权排序

不断合并连通块以及回答询问,每个连通块建权值线段树

 

  • PoPoQQQ2015年3月13日 下午7:44 回复

    线段树的合并如果没有重复元素是O(nlogn)的,有就是O(nlog^2n)

    #1  
    • 牧尘2016年4月1日 下午11:15 回复

      %%%%%PO姐

      #11