BZOJ_3545_[ONTAK2010]Peaks_主席树+倍增+kruscal重构树
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
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
1
-1
8
HINT
【数据范围】
N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。
可以证明我们从一个点出发，走最小生成树上的边不会使经过的点变少。
于是需要想出一种方法能够快速找到所有长度小于等于x的边。
kruscal重构树建树方法：把边排序，对于一条边连接两个不同的连通块这种情况，我们新建一个结点。
两个连通块的父亲和其并查集的父亲指向新建的点，令边权为实际的边权。
这样我们得到了一棵结点数为2n-1的树。
这个树有一些性质：
1.每个叶子结点对应原树的结点，同时每个叶子结点向上找只会找到新建的结点。
2.对于原生成树的一个边权小于x的连通块，可以用kruscal重构树中的一个子树来表示。
根据这两个性质，我们处理每次询问，倍增一下找到边权小于x最高的位置。
然后相当于求一个子树第K大权值，用dfs序+主席树写一下即可。
需要注意的是，BZOJ最后一个点的图不连通。
代码：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 1000000001
inline char nc() {
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
int rd() {
int x=0; char s=nc();
while(s<'0'||s>'9') s=nc();
while(s>='0'&&s<='9') x=(x<<3)+(x<<1)+s-'0',s=nc();
return x;
}
#define N 200050
#define M 500050
int head[N],to[N],nxt[N],val[N],fa[N],cnt,n,m,Q,h[N],f[22][N],dfn[N],son[N],tot,siz[N*20],ls[N*20],rs[N*20],se[N],root[N],H[N];
int find(int x) {
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void add(int u,int v) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt;
}
struct E {
int a,b,c;
bool operator < (const E &x) const {
return c<x.c;
}
}e[M];
void insert(int l,int r,int v,int x,int &y) {
y=++tot; siz[y]=siz[x]+1;
if(l==r) return ;
int mid=(l+r)>>1;
if(v<=mid) rs[y]=rs[x],insert(l,mid,v,ls[x],ls[y]);
else ls[y]=ls[x],insert(mid+1,r,v,rs[x],rs[y]);
}
int qk(int l,int r,int k,int x,int y) {
if(l==r) return l;
int mid=(l+r)>>1;
int sizls=siz[ls[y]]-siz[ls[x]];
if(k<=sizls) return qk(l,mid,k,ls[x],ls[y]);
else return qk(mid+1,r,k-sizls,rs[x],rs[y]);
}
void dfs(int x) {
H[x]=1;
int i;
if(x<=n) se[x]=1,dfn[x]=++dfn[0],insert(-maxn,maxn,h[x],root[dfn[0]-1],root[dfn[0]]);
else dfn[x]=dfn[0]+1;
for(i=head[x];i;i=nxt[i]) {
f[0][to[i]]=x;
dfs(to[i]);
se[x]+=se[to[i]];
}
son[x]=dfn[0];
}
int main() {
n=rd(); m=rd(); Q=rd();
int i,j,x,v,k; tot=n;
for(i=1;i<=n;i++) h[i]=rd();
for(i=1;i<=m;i++) {
e[i].a=rd(); e[i].b=rd(); e[i].c=rd();
}
sort(e+1,e+m+1);
for(i=1;i<=2*n;i++) fa[i]=i;
for(i=1;i<=m;i++) {
int dx=find(e[i].a),dy=find(e[i].b);
if(dx==dy) continue;
tot++; fa[dx]=tot; fa[dy]=tot; add(tot,dx); add(tot,dy); val[tot]=e[i].c;
}
for(i=tot;i>=1;i--) if(!H[i]) dfs(i);
tot=0;
int ln=n<<1;
for(i=1;(1<<i)<ln;i++) {
for(j=1;j<ln;j++) {
f[i][j]=f[i-1][f[i-1][j]];
}
}
while(Q--) {
v=rd(); x=rd(); k=rd();
for(i=21;i>=0;i--) {
if(f[i][v]&&val[f[i][v]]<=x) v=f[i][v];
}
k=se[v]-k+1;
if(k<=0) puts("-1");
else printf("%d\n",qk(-maxn,maxn,k,root[dfn[v]-1],root[son[v]]));
}
}