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
10
9
-1
题外话：
这题是bzoj3545的强化版，关于bzoj3545的做法，我等蒟蒻只想到了用平衡树（或FHQtreap)+并查集搞一搞，不过只能离线做，对于这题要求的在线那是万万做不到的。
正题：
首先要知道最小生成树在本题的作用，最小生成树能够在每条边都最短的情况下让该图联通，然而本题还需要在某种结构上查找，于是我们在做最小生成树的时候，用并查集将每一个点变成叶子节点，用边权作为父节点来连接几个叶节点。
这就类似于重新建了棵树，而且我们是做最小生成树，那么每个作为子节点的权值必然小于等于父节点。于是我们用倍增在这棵树上快速找到最高的合法的V点，以V为根节点的子树必然都可以找到，用dfs序让这棵树能够序号连续，但是只有作为山峰的点才需要插值，作为边权的点就直接沿袭上一棵主席树即可。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#define N 130000
int root[N*2],q[N*2],ls[N*18],rs[N*18],c[N*18];
int n,m,Q,wz[N],val[N*2],f[N*2],fa[N*2][18],tou[N*2],dd,top;
int st[N*2],ed[N*2],tot,ma[N*2][18];
bool vis[N];
struct aa{int len,x,y;
}dz[N*6];
struct pp{int va,pos;
}poi[N];
struct az{int p,next;
}da[N*4];
inline bool cmp(const aa a,const aa b){
return a.len<b.len;}
inline bool cm(pp a,pp b){
return a.va<b.va;}
int build(int l,int r){int rt=++tot;c[rt]=0;if (l==r)return rt;int mid=(l+r)/2;if (l<=mid)ls[rt]=build(l,mid);if (mid+1<=r)rs[rt]=build(mid+1,r);return rt;
}
int update(int rt,int pos){int tmp,rt1;tmp=rt1=++tot;int l=1;int r=n;c[rt1]=c[rt]+1;while (l<r){int mid=(l+r)/2;if (pos<=mid){ls[rt1]=++tot;rs[rt1]=rs[rt];rt1=ls[rt1];rt=ls[rt];r=mid;}else{rs[rt1]=++tot;ls[rt1]=ls[rt];rt1=rs[rt1];rt=rs[rt];l=mid+1;} c[rt1]=c[rt]+1;}return tmp;
}
int query(int rt,int rt1,int l,int r,int pos){while (l<r){int mid=(l+r)/2;int num=c[ls[rt1]]-c[ls[rt]];if (pos<=num){rt1=ls[rt1];rt=ls[rt];r=mid;}else{pos-=num;rt1=rs[rt1];rt=rs[rt];l=mid+1;} }return poi[l].va;
}
//-----------------------------------------主席树
void add(int x,int y){da[++dd].p=y;da[dd].next=tou[x];tou[x]=dd;
}
//-----------------------------------------建边
int find(int x){if (f[x]==x)return x;f[x]=find(f[x]);return f[x];
}
//-----------------------------------------并查集
int findd(int x,int va){for (int i=17;i>=0;i--)if (fa[x][i]&&ma[x][i]<=va)x=fa[x][i];return x;
}
void dfs(int x){q[++top]=x;vis[x]=1;for (int i=1;i<=17;i++){fa[x][i]=fa[fa[x][i-1]][i-1];ma[x][i]=std::max(ma[x][i-1],ma[fa[x][i-1]][i-1]);if (!fa[x][i])break;}for (int i=tou[x];i;i=da[i].next){fa[da[i].p][0]=x;ma[da[i].p][0]=val[x];dfs(da[i].p);}if(x>n)q[++top]=x;
}
//-----------------------------------------dfs序+倍增
void tree_build(){int nod=n;for (int i=1;i<=2*n;i++)f[i]=i;for (int i=1;i<=m;i++){int fx=find(dz[i].x);int fy=find(dz[i].y);if (fx!=fy){f[fx]=f[fy]=++nod;val[nod]=dz[i].len;add(nod,fx);add(nod,fy);if (nod==2*n-1)break;}}for (int i=1;i<=n;i++)if (!vis[i])dfs(find(i));for (int i=1;i<=top;i++){int x=q[i];if (x<=n)root[i]=update(root[i-1],wz[x]);else{root[i]=root[i-1];if (!st[x])st[x]=i;else ed[x]=i;}}
}
void tree_solve(){int last;last=-1;for (int i=1;i<=Q;i++){int x,v,k;scanf("%d%d%d",&v,&x,&k);if (last!=-1)v=v^last,x=x^last,k=k^last;int nods=findd(v,x);if (c[root[ed[nods]]]-c[root[st[nods]]]<k)printf("-1\n"),last=-1;else {last=query(root[st[nods]],root[ed[nods]],1,n,c[root[ed[nods]]]-c[root[st[nods]]]+1-k);printf("%d\n",last);}}
}
//-----------------------------------------主程序
int main(){scanf("%d%d%d",&n,&m,&Q);for (int i=1;i<=n;i++)scanf("%d",&poi[i].va),poi[i].pos=i;std::sort(poi+1,poi+n+1,cm);root[0]=build(1,n);for (int i=1;i<=n;i++)wz[poi[i].pos]=i;for (int i=1;i<=m;i++)scanf("%d%d%d",&dz[i].x,&dz[i].y,&dz[i].len);std::sort(dz+1,dz+m+1,cmp);tree_build();tree_solve();return 0;
}