bzoj 3545: [ONTAK2010]Peaks (splay启发式合并)

在Bytemountains有N座山峰，每座山峰有他的高度h_i。有些山峰之间有双向道路相连，共M条路径，每条路径有一个困难值，这个值越大表示越难走，现在有Q组询问，每组询问询问从点v开始只经过困难值小于等于x的路径所能到达的山峰中第k高的山峰，如果无解输出-1。

第一行三个数N，M，Q。
第二行N个数，第i个数为h_i
接下来M行，每行3个数a b c，表示从a到b有一条困难值为c的双向路径。
接下来Q行，每行三个数v x k，表示一组询问。

对于每组询问，输出一个整数表示答案。

【数据范围】

N<=10^5, M,Q<=5*10^5，h_i,c,x<=10^9。

By Sbullet

明明记得这题放过题解，找不到了，那就再放一次。。。

对于每个并查集开一颗splay，合并并查集的同时启发式合并splay

启发式合并是什么意思呢，小的splay暴力插入大的中.......

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<string>
#include<climits>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define N 500010
#define M 2500010
using namespace std;
inline int read()
{int x=0,f=1;char ch;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m,q,ans[N];
int tr[M][2],fa[M],size[M];
int root[N],v[M],sz;
inline void pushup(int k){size[k]=size[tr[k][0]]+size[tr[k][1]]+1;}
inline void rotate(int x,int &k)
{int y=fa[x],z=fa[y],l,r;l=tr[y][1]==x;r=l^1;if(k==y)k=x;else tr[z][tr[z][1]==y]=x;fa[x]=z,fa[y]=x,fa[tr[x][r]]=y;tr[y][l]=tr[x][r],tr[x][r]=y;pushup(y);pushup(x);
}
inline void splay(int x,int &k)
{while(x!=k){int y=fa[x],z=fa[y];if(y!=k){if(tr[y][0]==x^tr[z][0]==y)rotate(x,k);else rotate(y,k);}rotate(x,k);}
}
inline int find_k(int k,int rk)
{int l=tr[k][0],r=tr[k][1];if(size[r]+1==rk)return v[k];else if(size[r]>=rk)return find_k(r,rk);else return find_k(l,rk-size[r]-1);
}
int t1,t2;
inline void ins(int &k,int x,int last,int &rt)
{if(!k){k=++sz;fa[k]=last,size[k]=1,v[k]=x;splay(k,rt);return;}else if(v[k]>=x)ins(tr[k][0],x,k,rt);else ins(tr[k][1],x,k,rt);
}
inline void merge(int k,int &rt)
{if(!k)return;merge(tr[k][0],rt);merge(tr[k][1],rt);	ins(rt,v[k],0,rt);
}int pre[N],h[N];
int find(int x){return x==pre[x]?x:pre[x]=find(pre[x]);} 
inline void work(int a,int b)
{int rb=root[b],ra=root[a];if(size[root[b]]>size[root[a]])swap(a,b);pre[b]=a;merge(root[b],root[a]);
}
struct edge{int x,y,c;}e[M];
bool operator < (edge a,edge b){return a.c<b.c;}
struct qry{int v,x,k,id;}ak[M]; 
bool operator < (qry a,qry b){return a.x<b.x;}
void init()
{n=read(),m=read(),q=read();for(int i=1;i<=n;i++)h[i]=read();for(int i=1;i<=n;i++){pre[i]=i;ins(root[i],h[i],0,i);}for(int i=1;i<=m;i++){e[i].x=read();e[i].y=read();e[i].c=read();}sort(e+1,e+1+m);for(int i=1;i<=q;i++){ak[i].v=read();ak[i].x=read();ak[i].k=read();ak[i].id=i;}sort(ak+1,ak+1+q);
}
int main()
{
//	freopen("in.txt","r",stdin);
//	freopen("my.txt","w",stdout);init();int i=0,j=1;for(i=1;i<=q;i++){while(e[j].c<=ak[i].x&&j<=m){int a=e[j].x,b=e[j].y;int fa=find(a),fb=find(b);if(fa!=fb)work(fa,fb);j++;}int t=find(ak[i].v);if(size[root[t]]<ak[i].k)ans[ak[i].id]=-1;else ans[ak[i].id]=find_k(root[t],ak[i].k);}for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}