【BZOJ3551】Peaks加强版（Kruskal重构树，主席树）

题面

BZOJ

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。

题解

很明显的克鲁斯卡尔重构树之后直接用主席树维护区间第\(K\)大。

注意克鲁斯卡尔重构树维护的最小生成树的边权是放在点上的。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

using namespace std;

#define ll long long

#define MAX 200500

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

struct Line{int v,next;}e[MAX];

int h[MAX],cnt=1;

inline void Add(int u,int v){e[cnt]=(Line){v,h[u]};h[u]=cnt++;}

struct edge{int u,v,w;}E[MAX<<2];

bool operator<(edge a,edge b){return a.w<b.w;}

int f[MAX],tot;

int getf(int x){return x==f[x]?x:f[x]=getf(f[x]);}

int n,m,Q,a[MAX];

int p[20][MAX],dis[MAX];

int dfn[MAX],low[MAX],ln[MAX],tim;

void dfs(int u,int ff)

{

	if(u<=n)dfn[u]=low[u]=++tim,ln[tim]=u;

	else dfn[u]=1e9,low[u]=0;

	p[0][u]=ff;

	for(int i=1;i<20;++i)p[i][u]=p[i-1][p[i-1][u]];

	for(int i=h[u];i;i=e[i].next)

		dfs(e[i].v,u),dfn[u]=min(dfn[u],dfn[e[i].v]),low[u]=max(low[u],low[e[i].v]);

}

int rt[MAX],S[MAX],top;

struct Node{int ls,rs,v;}t[MAX*20];

int num;

void modify(int &x,int l,int r,int p)

{

	t[++num]=t[x];++t[x=num].v;if(l==r)return;

	int mid=(l+r)>>1;

	if(p<=mid)modify(t[x].ls,l,mid,p);

	else modify(t[x].rs,mid+1,r,p);

}

int Query(int A,int B,int l,int r,int K)

{

	if(l==r)return S[l];

	int mid=(l+r)>>1,sum=t[t[A].rs].v-t[t[B].rs].v;

	if(sum>=K)return Query(t[A].rs,t[B].rs,mid+1,r,K);

	else return Query(t[A].ls,t[B].ls,l,mid,K-sum);

}

int main()

{

	n=read();m=read();Q=read();

	for(int i=1;i<=n;++i)S[i]=a[i]=read();

	sort(&S[1],&S[n+1]);top=unique(&S[1],&S[n+1])-S-1;

	for(int i=1;i<=n;++i)a[i]=lower_bound(&S[1],&S[top+1],a[i])-S;

	for(int i=1;i<=m;++i)

	{

		int u=read(),v=read(),w=read();

		E[i]=(edge){u,v,w};

	}

	sort(&E[1],&E[m+1]);

	for(int i=1;i<=n;++i)f[i]=i;tot=n;

	for(int i=1;i<=m;++i)

	{

		int u=getf(E[i].u),v=getf(E[i].v);

		if(u==v)continue;++tot;

		f[tot]=f[u]=f[v]=tot;dis[tot]=E[i].w;

		Add(tot,u);Add(tot,v);

	}

	dfs(tot,0);

	for(int i=1;i<=n;++i)modify(rt[i]=rt[i-1],1,top,a[ln[i]]);

	int lans=0;

	while(Q--)

	{

		int v=read(),x=read(),K=read();

		if(lans!=-1)v^=lans,x^=lans,K^=lans;

		for(int i=19;~i;--i)

			if(p[i][v]&&dis[p[i][v]]<=x)

				v=p[i][v];

		if(low[v]-dfn[v]+1<K)lans=-1;

		else lans=Query(rt[low[v]],rt[dfn[v]-1],1,top,K);

		printf("%d\n",lans);

	}

	return 0;

}