P4197 Peaks

题目描述

在\(\text{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 \le 10^5\), \(0 \le M,Q \le 5\times 10^5\),\(h_i,c,x \le 10^9\) 。

---

恩，顺手学了一下重构树

觉得这篇洛谷日报讲的不错

说一下感受。

还是有点码量的，不太好调，写的时候认真一点，注意空间。

---

Code:

#include <cstdio>

#include <algorithm>

const int N=1e5+10;

const int M=5e5+10;

int n,m,q,F[N<<1],dfn[N<<1],low[N<<1],dfs_clock,ha[N<<1],f[N<<1][19],poi[N<<1];

int th[N],h[N];

struct node

{

    int u,v,w;

    bool friend operator <(node n1,node n2){return n1.w<n2.w;}

}e[M];

int Find(int x){return F[x]=F[x]==x?x:Find(F[x]);}

int Next[N<<1],to[N<<1],head[N<<1],cnt;

void add(int u,int v){to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;}

void dfs(int now)

{

    for(int i=1;f[now][i-1];i++) f[now][i]=f[f[now][i-1]][i-1];

    dfn[now]=++dfs_clock,ha[dfs_clock]=now;

    for(int i=head[now];i;i=Next[i])

        dfs(to[i]);

    low[now]=dfs_clock;

}

int sum[N*30],ch[N*30][2],root[N<<1],tot;

#define ls ch[now][0]

#define rs ch[now][1]

#define ols ch[las][0]

#define ors ch[las][1]

int rebuild(int las,int l,int r,int pos)

{

    int now=++tot,mid=l+r>>1;

    if(l==r) return sum[now]=sum[las]+1,now;

    if(pos<=mid)

    {

        ls=rebuild(ols,l,mid,pos);

        rs=ors;

    }

    else

    {

        ls=ols;

        rs=rebuild(ors,mid+1,r,pos);

    }

    return sum[now]=sum[ls]+sum[rs],now;

}

int query(int now,int las,int l,int r,int k)

{

    if(k>sum[now]-sum[las]) return 0;

    if(l==r) return l;

    int mid=l+r>>1;

    if(sum[rs]-sum[ors]>=k)

        return query(rs,ors,mid+1,r,k);

    else

        return query(ls,ols,l,mid,k-sum[rs]+sum[ors]);

}

int find(int v,int x)//v不大于x的点

{

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

        if(poi[f[v][i]]<=x)

            v=f[v][i];

    return v;

}

int main()

{

    scanf("%d%d%d",&n,&m,&q);

    int n_=n;

    for(int i=1;i<=n;i++) scanf("%d",h+i),th[i]=h[i];

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

        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);

    std::sort(e+1,e+1+m);

    std::sort(th+1,th+1+n);

    int m_=std::unique(th+1,th+1+n)-th-1;

    for(int i=1;i<=n;i++) h[i]=std::lower_bound(th+1,th+1+m_,h[i])-th;

    th[0]=-1,poi[0]=0x7fffffff;

    for(int i=1;i<=n*2;i++) F[i]=i;

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

    {

        int u=e[i].u,v=e[i].v,w=e[i].w;

        int rt1=Find(u),rt2=Find(v);

        if(rt1==rt2) continue;

        F[rt1]=F[rt2]=f[rt1][0]=f[rt2][0]=++n;

        add(n,rt1),add(n,rt2);

        poi[n]=w;

    }

    dfs(n);

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

    {

        if(ha[i]<=n_)

            root[i]=rebuild(root[i-1],1,m_,h[ha[i]]);

        else

            root[i]=root[i-1];

    }

    for(int anc,v,x,k,i=1;i<=q;i++)

    {

        scanf("%d%d%d",&v,&x,&k);

        anc=find(v,x);

        printf("%d\n",th[query(root[low[anc]],root[dfn[anc]-1],1,m_,k)]);

    }

    return 0;

}

---

2018.10.16