题目链接
(Solution)
首先来介绍一下kruskal重构树:详见
知道kruskal重构树后这一道题就可以几乎没了.
利用kruskal重构树的性质,一个节点的左右儿子都比他小(其实就是一个堆),所以从点(v)开始只经过困难值小于等于(x)的路径实际上就是找到一个权值小于等于(x)的且深度最小的点
我们将这个点叫做(K).那么点(v)可以走的路径就是点(K)的子树.现在要求第k高的山峰,这直接用主席树+dfs序搞一搞就好了
(Code)
#include<bits/stdc++.h>
using namespace std;
const int N=200011;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
return f*x;
}
struct node1 {
int to,next;
}e[500001];
struct node{
int x,y,v;
}b[500001];
struct node2 {
int l,r,v;
}a[N*20];
int root,tot,res,cnt,n,m,t,h[N],pre[N],head[N],T[N];
int fa[N][21],dep[N],bin[101],val[N],r[N],l[N],tail[N];
void add(int x,int y){ e[++cnt].to=y,e[cnt].next=head[x],head[x]=cnt; }
int find(int x){ return pre[x]==x?x:pre[x]=find(pre[x]); }
bool cmp(const node & a , const node & b ){ return a.v<b.v; }
int query(int x,int v){
for(int i=19;i>=0;i--)
if(dep[x]>=bin[i]&&val[fa[x][i]]<=v)
x=fa[x][i];
return x;
}
void dfs(int x){
if(x<=n)
h[++tot]=tail[x];
l[x]=tot;
for(int i=1;i<=16;i++)
if(dep[x]>=bin[i])
fa[x][i]=fa[fa[x][i-1]][i-1];
for(int i=head[x];i;i=e[i].next)
dep[e[i].to]=dep[x]+1,fa[e[i].to][0]=x,dfs(e[i].to);
r[x]=tot;
}
void build(){
res=n,sort(b+1,b+1+m,cmp);
for(int i=1;i<=m;i++){
int fx=find(b[i].x),fy=find(b[i].y);
if(fx!=fy)
val[++res]=b[i].v,pre[fx]=res,pre[fy]=res,add(res,fx),add(res,fy);
if(res==n*2-1)
break;
}
}
void insert(int &k,int l,int r,int v){
a[++root]=a[k],k=root,a[k].v++;
if(l==r) return ;
int mid=(l+r)>>1;
if(v<=mid)
insert(a[k].l,l,mid,v);
else insert(a[k].r,mid+1,r,v);
}
int answer(int x,int k,int l,int r,int v){
if(l==r) return l;
int mid=(l+r)>>1,pos=a[a[k].l].v-a[a[x].l].v;
if(v<=pos)
return answer(a[x].l,a[k].l,l,mid,v);
else return answer(a[x].r,a[k].r,mid+1,r,v-pos);
}
void solve(){
int last=-1;
while(t--){
int v=read(),x=read(),k=read();
if(last!=-1)
v^=last,x^=last,k^=last;
int now=query(v,x);
(r[now]-l[now]<k)?last=-1:last=tail[answer(T[l[now]],T[r[now]],1,n,r[now]-l[now]-k+1)];
printf("%d
",last);
}
}
int main(){
n=read(),m=read(),t=read(),bin[0]=1;
for(int i=1;i<=n;i++)
tail[i]=read();
for(int i=1;i<n*2;i++)
pre[i]=i;
for(int i=1;i<=19;i++)
bin[i]=bin[i-1]<<1;
for(int i=1;i<=m;i++)
b[i].x=read(),b[i].y=read(),b[i].v=read();
build(),dfs(find(1));
sort(tail+1,tail+1+n);
int k=unique(tail+1,tail+1+n)-tail-1;
for(int i=1;i<=n;i++)
T[i]=T[i-1],insert(T[i],1,k,lower_bound(tail+1,tail+1+k,h[i])-tail);
n=k,solve();
}