Peaks 加强版-题解

· · 题解

Peaks 加强版（强制在线版）-题解

题面

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

算法标签

题目分析

寻找只经过困难值小于等于 x 的路径所能到达的山峰，即寻找点 p 与哪些点之间的路径最大边权小于等于 x。Kruskal 重构树（从小到大便排序）之后，两个节点的 \mathrm{LCA} 点值即为图上这两点间路径最大边权的最小值，所以我们就可以使用这一算法处理图，处理完成之后这棵树构成一个大根堆。

我们从点 p 开始走，很显然，当我们只能往上走到权值小于 x 的点，如果再往上，就会遇到边权更大的边了。这种单调的性质使我们能够使用倍增向上跳到这个点。\mathrm{LCA}(p,q) 在这个点以下的 q 肯定都是这个点子树中的节点。我们要求的就转换为了这个点子树中高度第 k 高的山峰。这就可以用主席树了。

实现细节

按照 Kruskal 重构出来的 dfs 序建立主席树，记录每个节点子树管辖范围的开始对应根节点和结束对应根节点。原图中的节点在重构的树中全是叶子节点，所以插入操作只在叶子节点存在。接着就是主席树求第 k 大的板子了。

完整代码

#include<bits/stdc++.h>

#define  Int  long long int
#define  Tem  template
#define  Pub  public

using std::min;using std::max;

int n,m,q;
Int h[100005];
Int num[100005],newn;//对h的需离散化 

class Edge{//边 
Pub:int a,b;Int c;
}e[500005];
class HJT{//主席树 
Pub:int size;
    int ls,rs;
}t[5000000];
int root[100005];
int cnt_HJT;
int ins(int RT,int L,int R,int x){//主席树插入 
    int rt=++cnt_HJT;
    t[rt]=t[RT];
    ++t[rt].size;
    if(L<R){
        int M=(L+R)/2;
        if(x<=M)
            t[rt].ls=ins(t[RT].ls,L,M,x);
        else
            t[rt].rs=ins(t[RT].rs,M+1,R,x);
    }
    return rt;
}
int kth(int RT1,int RT2,int L,int R,int k){//主席树查询 
    if(t[RT2].size-t[RT1].size<k)return -1;
    if(L==R)return L|R;
    int M=(L+R)/2;
    if(t[t[RT2].rs].size-t[t[RT1].rs].size>=k)
        return kth(t[RT1].rs,t[RT2].rs,M+1,R,k);
    else
        return kth(t[RT1].ls,t[RT2].ls,L,M,k-(t[t[RT2].rs].size-t[t[RT1].rs].size));
}

class Node{//重构树的节点 
Pub:Int c[20],cc;
    int ls,rs,fa[20];
    int boss;
    int lrt,rrt;
}d[200005];
int cnt_node;

int Boss(int x){//并查集路径压缩 
    if(d[x].boss!=x)d[x].boss=Boss(d[x].boss);
    return d[x].boss;
}
void Merge(int x,int y,Int c){//并查集合并与重构树新建节点 
    x=Boss(x),y=Boss(y);
    if(x==y)return;
    d[x].fa[0]=d[x].boss=d[y].fa[0]=d[y].boss=++cnt_node;
    d[x].c[0]=d[y].c[0]=c;
    d[cnt_node].boss=cnt_node;
    d[cnt_node].cc=c;
    d[cnt_node].ls=x;d[cnt_node].rs=y;
}
void kruskal(){//Kruskal重构树 
    for(int i=1;i<=n;++i)d[i].boss=i;
    std::sort(e+1,e+1+m,[](Edge a,Edge b)->bool{return a.c<b.c;});
    for(int i=1;i<=m;++i)
        Merge(e[i].a,e[i].b,e[i].c);
}

int cnt_rt;
void dfs(int x){//倍增预处理 
    if(x==0)return;
    d[x].lrt=cnt_rt;
    for(int i=1;i<=18;++i){
        d[x].fa[i]=d[d[x].fa[i-1]].fa[i-1];
        d[x].c[i]=max(d[x].c[i-1],d[d[x].fa[i-1]].c[i-1]);
    }
    if(x<=n){
        root[cnt_rt+1]=ins(root[cnt_rt],1,newn,h[x]);
        ++cnt_rt;
    }
    dfs(d[x].ls);dfs(d[x].rs);
    d[x].rrt=cnt_rt;
}

int lastans;
void query(int st,Int x,int k){//查询 
    for(int i=18;i>=0;--i)
        if(d[st].c[i]<=x&&d[st].fa[i])
            st=d[st].fa[i];
    int ans;
    if(d[st].cc>x)ans=-1;
    else ans=kth(root[d[st].lrt],root[d[st].rrt],1,newn,k);
    if(ans==-1)printf("-1\n"),lastans=0;
    else printf("%lld\n",num[ans]),lastans=num[ans];
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    cnt_node=n;

    for(int i=1;i<=n;++i){
        scanf("%lld",&h[i]);
        num[i]=h[i];
    }
    std::sort(num+1,num+1+n);
    newn=std::unique(num+1,num+1+n)-num-1;
    for(int i=1;i<=n;++i)
        h[i]=std::lower_bound(num+1,num+1+newn,h[i])-num;

    for(int i=1;i<=m;++i)
        scanf("%d%d%lld",&e[i].a,&e[i].b,&e[i].c);
    kruskal();
    dfs(cnt_node);
    while(~--q){
        int st;Int x;int k;
        scanf("%d%lld%d",&st,&x,&k);//注意强制在线的转换 
        st=st^lastans;
        x=x^lastans;
        k=k^lastans;
        query(st,x,k);
    }

    return 0;
}