Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 2038  Solved: 535

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。

 

Source

 

Kruskal  启发式合并 树 treap 脑洞题

将询问离线，按询问x值从小到大排序，回答每个询问前将x值小于询问值的边加进集合，进行启发式合并。

用treap维护集合内的结点，进行排名查询以回答询问。

 

要回答的是目标山的高度，不是编号←样例真是充满了误导性

 

算法比较好想，然而并不会写treap的启发式合并……

各种开脑洞，发现要么太难实现，要么实现了不能保证二叉树性质WAWAWA

依稀记得听说过可持久化treap的合并是以某个权值为界把treap拆分开，再合并成一整棵新树，想想就好难写。

最后放弃了挣扎，选择了暴力把一棵treap上的点全建到另一棵treap上。

然而一对拍又挂了，检查了好久好久，发现合并时候少传了一个地址。

于是一下午+半个晚上就水过去了。

 

随机数种子很好用，并没有特殊的意义(认真脸)

1 /*by SilverN*/  2 #include
     
        3 #include
      
         4 #include
       
          5 #include
        
           6 #include
         
            7 #include
          
            8 using namespace std; 9 const int mxn=120010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<'0' || ch>'9'){ if(ch=='-')f=-1;ch=getchar();} 13 while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int x,y,w; 18 bool operator < (edge b)const{ return w
           
            t[rt].rand){ 79 Rt(rt); 80 } 81 } 82 else{ 83 insert(v,c,t[rt].r); 84 if(t[t[rt].r].rand>t[rt].rand){ 85 Lt(rt); 86 } 87 } 88 return; 89 } 90 void Merge(int &x,int &y){ //y也会被改变，需要传地址 91 if(!x)return; 92 Merge(t[x].l,y); 93 Merge(t[x].r,y); 94 int tmp=x; 95 x=0; 96 insert(t[tmp].v,t[tmp].cnt,y); 97 bin[++top]=tmp; 98 return; 99 }100 int ask_rank(int rt,int k){101 if(!rt)return 0;102 if(t[t[rt].r].sz>=k)return ask_rank(t[rt].r,k);103 else if(t[t[rt].r].sz+t[rt].cnt>=k)return t[rt].v;104 else return ask_rank(t[rt].l,k-t[t[rt].r].sz-t[rt].cnt);105 }106 void link(int u,int v){107 u=find(u);v=find(v);108 if(u==v)return;109 if(t[u].sz