bzoj 3545/3551: [ONTAK2010]Peaks -- 主席树，最小生成树，倍增

3545: [ONTAK2010]Peaks

Time Limit: 10 Sec Memory Limit: 128 MB

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。

Source

首先一定是走最小生成树上的边是最优的，然后我们按建树的顺序合并节点，这样我们发现一个子树里的边权都小于他本身

然后查询就是倍增找到当前点能到的最远的祖先，就变成了查询子树的第k大，然后用主席树维护就可以了

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define M 6000010

#define N 500010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int n,m,Q;

int h[N];

struct qaz{int a,b,c;}e[N],tp[N];

bool cmp(qaz a,qaz b){return a.c<b.c;}

int fa[N],mz;

int findf(int x){return x==fa[x]?x:fa[x]=findf(fa[x]);}

int lj[N],fro[N],to[N],cnt;

void add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}

bool vs[N];

int st[N],ed[N],tim,dep[N];

int Fa[][],rt[N];

int ls[M],rs[M],sz[M],tot;

void add(int lst,int &p,int l,int r,int x)

{

    p=++tot;

    ls[p]=ls[lst];rs[p]=rs[lst];

    sz[p]=sz[lst]+;

    if(l==r) return;

    int mid=l+r>>;

    if(x<=mid) add(ls[lst],ls[p],l,mid,x);

    else add(rs[lst],rs[p],mid+,r,x);

}

void dfs(int x)

{

    st[x]=++tim;vs[x]=;

    dep[x]=dep[Fa[x][]]+;

    if(x<=n) add(rt[tim-],rt[tim],,n,h[x]);

    else rt[tim]=rt[tim-];

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

    {

        if(dep[x]<(<<i)) break;

        Fa[x][i]=Fa[Fa[x][i-]][i-];

    }

    for(int i=lj[x];i;i=fro[i])

    {

        Fa[to[i]][]=x;

        dfs(to[i]);

    }

    ed[x]=tim;

}

int fd(int x,int y,int l,int r,int k)

{

    if(l==r) return tp[l].c;

    int mid=l+r>>;

    if(sz[rs[x]]-sz[rs[y]]>=k) return fd(rs[x],rs[y],mid+,r,k);

    else return fd(ls[x],ls[y],l,mid,k-sz[rs[x]]+sz[rs[y]]);

}

int main()

{

    mz=n=rd();m=rd();Q=rd();

    for(int i=;i<=n;i++) tp[i].c=rd(),tp[i].a=i;

    sort(tp+,tp+n+,cmp);

    for(int i=;i<=n;i++)

    {

        if(i>&&tp[i].c==tp[i-].c) h[tp[i].a]=h[tp[i-].a];

        else h[tp[i].a]=i;

    }

    for(int i=,a,b,c;i<=m;i++)

    {

        a=rd();b=rd();c=rd();

        e[i]=(qaz){a,b,c};

    }

    sort(e+,e+m+,cmp);

    for(int i=;i<n+n;i++) fa[i]=i;

    for(int i=,x,y;i<=m;i++)

    {

        x=findf(e[i].a);y=findf(e[i].b);

        if(x==y) continue;

        fa[x]=fa[y]=++mz;

        h[mz]=e[i].c;

        add(mz,x);add(mz,y);

        if(mz==n*-) break;

    }

    for(int i=;i<=n;i++) if(!vs[i]) dfs(findf(i));

    int x,y,z,lans=-,Rt;

    while(Q--)

    {

        x=rd();y=rd();z=rd();

        Rt=x;

        for(int i=;i>=;i--)

            if(dep[Rt]>(<<i)&&h[Fa[Rt][i]]<=y)  Rt=Fa[Rt][i];

        if(sz[rt[ed[Rt]]]-sz[rt[st[Rt]-]]<z) lans=-;

        else lans=fd(rt[ed[Rt]],rt[st[Rt]-],,n,z);

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

    }

    return ;

}

秒客网