[文章目录]
Description
在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
将询问离线，按照x排序。对于递增的x，我们向图中加边，每个联通块维护一个权值线段树，连边的时候权值线段树合并。并查集记录所在联通块。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100100
int n,m,q,h[N],b[N],c[N],tot;
inline void read(int &x)
{
char ch=getchar(); x=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
}
inline int getid(int x) {return lower_bound(c+1,c+tot+1,x)-c;}
struct edge {
int x,y,w;
}ed[N*5];
bool cmp(edge x,edge y){return x.w<y.w;}
struct ques {
int v,x,k,id;
}qu[N*5];
int ans[N*5];
bool cmp1(ques x,ques y){return x.x<y.x;}
struct seg
{
int ls,rs,siz;
}s[N*18];
int se,rt[N],fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int merge(int x,int y)
{
if(!x||!y) return x|y; s[x].siz+=s[y].siz;
s[x].ls=merge(s[x].ls,s[y].ls);
s[x].rs=merge(s[x].rs,s[y].rs);
return x;
}
void insert(int l,int r,int &x,int z)
{
x=++se; s[x].siz=1;
if(l==r) return ; int mid=(l+r)>>1;
if(z<=mid) insert(l,mid,s[x].ls,z);
else insert(mid+1,r,s[x].rs,z);
}
int query(int l,int r,int x,int y)
{
if(l==r) return c[l];
int mid=(l+r)>>1,z=s[s[x].ls].siz;
if(y<=z) return query(l,mid,s[x].ls,y);
else return query(mid+1,r,s[x].rs,y-z);
}
inline void Ins(int x,int y)
{
x=find(x); y=find(y);
if(x!=y) merge(rt[x],rt[y]),fa[y]=x;
}
int main()
{
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=n;++i) {read(h[i]); b[i]=h[i]; fa[i]=i;}
sort(b+1,b+n+1); c[++tot]=b[1];
for(int i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
for(int i=1;i<=m;++i) {read(ed[i].x); read(ed[i].y); read(ed[i].w);}
sort(ed+1,ed+m+1,cmp);
for(int i=1;i<=q;++i) {qu[i].id=i; read(qu[i].v); read(qu[i].x); read(qu[i].k);}
sort(qu+1,qu+q+1,cmp1);
for(int i=1;i<=n;++i) insert(1,tot,rt[i],getid(h[i]));
int x=1,tmp;
for(int i=1;i<=q;++i)
{
while(x<=m&&ed[x].w<=qu[i].x) Ins(ed[x].x,ed[x].y),x++;
tmp=find(qu[i].v);
if(s[rt[tmp]].siz<qu[i].k) ans[qu[i].id]=-1;
else ans[qu[i].id]=query(1,tot,rt[tmp],s[rt[tmp]].siz-qu[i].k+1);
}
for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
return 0;
}