题意
给定 (n) 个点 (m) 条边的无向图,点有点权,边有边权。具体来说,第 (i) 个点的点权是 (h_i),第 (i) 条边 ((a_i,b_i)) 的边权为 (c_i)。(q) 次询问,每次询问从某个点出发只经过边权小于等于 (x) 的边能到达的点中权值第 (k) 大的点的权值。
(1 leq n leq 10^5, 0leq m,q leq 5 imes 10^5, 0 leq h_i,c_i,x leq 10^9)
题解
考虑离线,把 (x) 排序,这样就变成了只有加边操作。
加边操作就是合并两个连通块。平衡树启发式合并?(log^2),慢走不送。
当然是线段树合并啦。这样可以做到 (O(n log n + q log n)) 的优秀复杂度。
# include <bits/stdc++.h>
const int N=100010,M=500010,INF=0x3f3f3f3f;
struct Node{
int lc,rc,sum;
}tree[N*50];
int cnt;
struct Edge{
int u,v,w;
bool operator < (const Edge &rhs) const{
return w<rhs.w;
}
}edge[M];
struct Queries{
int v,x,k,id;
bool operator < (const Queries &rhs) const{
return x<rhs.x;
}
}a[M];
int n,m,q;
int h[N];
int b[N],bcnt;
int f[N],root[N];
int ans[M];
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int find(int x){
return (f[x]==x)?x:(f[x]=find(f[x]));
}
inline int& lc(int x){
return tree[x].lc;
}
inline int& rc(int x){
return tree[x].rc;
}
void change(int &k,int l,int r,int x){
k=(k?k:++cnt);
++tree[k].sum;
if(l==r)
return;
int mid=(l+r)>>1;
if(x<=mid)
change(lc(k),l,mid,x);
else
change(rc(k),mid+1,r,x);
return;
}
int query(int now,int l,int r,int k){
if(l==r){
return l;
}
int mid=(l+r)>>1;
if(k<=tree[rc(now)].sum)
return query(rc(now),mid+1,r,k);
return query(lc(now),l,mid,k-tree[rc(now)].sum);
}
void merge(int &now,int pL,int pR,int l,int r){
if(!pL||!pR){
now=pL|pR;
return;
}
now=pL;
if(l==r){
tree[now].sum=tree[pL].sum+tree[pR].sum;
return;
}
int mid=(l+r)>>1;
merge(lc(now),lc(pL),lc(pR),l,mid),merge(rc(now),rc(pL),rc(pR),mid+1,r);
tree[now].sum=tree[lc(now)].sum+tree[rc(now)].sum;
return;
}
int main(void){
n=bcnt=read(),m=read(),q=read();
for(int i=1;i<=n;++i){
h[i]=b[i]=read();
}
for(int i=1;i<=m;++i){
edge[i].u=read(),edge[i].v=read(),edge[i].w=read();
}
for(int i=1;i<=q;++i){
a[i].id=i,a[i].v=read(),a[i].x=read(),a[i].k=read();
}
std::sort(edge+1,edge+1+m),std::sort(a+1,a+1+q);
std::sort(b+1,b+1+bcnt),bcnt=std::unique(b+1,b+1+bcnt)-(b+1);
for(int i=1;i<=n;++i){
h[i]=std::lower_bound(b+1,b+1+bcnt,h[i])-b;
f[i]=i,change(root[i],1,bcnt,h[i]);
}
int pt=1;
for(int i=1;i<=q;++i){
while(pt<=m&&edge[pt].w<=a[i].x){
int u=find(edge[pt].u),v=find(edge[pt].v);
if(u==v){
++pt;
continue;
}
f[u]=v;
merge(root[v],root[u],root[v],1,bcnt);
++pt;
}
int nrt=root[find(a[i].v)];
if(tree[nrt].sum<a[i].k){
ans[a[i].id]=-1;
}else{
ans[a[i].id]=b[query(nrt,1,bcnt,a[i].k)];
}
}
for(int i=1;i<=q;++i){
printf("%d
",ans[i]);
}
return 0;
}