Luogu

BZOJ强制在线版

分析

简化版题意:求所有能从点$v$走边权不超过$k$的边到达的点中第$k$高的高度。

边权不超过$k$,显然可以上$\texttt{Kruskal重构树}$。

于是建出树来,对于每次询问,树上倍增到最小的权值$\geq k$的点那里,然后此时答案就是子树中的第$k$大值。

对$\texttt{dfs}$序建一颗主席树就可以维护了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int M=1000000+10;

int n,m,q;
int height[N],S[N];
int root[N];
struct Save_Edge { int u,v,w; } E[M];
struct Edge { int v,nxt; } e[M<<1];
int head[N];
int f[20][N],pos[N],st[N],ed[N],dfs_clock=0;
int cnt,dis[N];
int rt[N],node_tot=0;
struct node { int lson,rson,sum; } t[N*20];

bool operator <(const Save_Edge a,const Save_Edge b) { return a.w<b.w; }

inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt].v=v,e[cnt].nxt=head[u],head[u]=cnt;
}
inline int find(int x) { return x==root[x]?x:root[x]=find(root[x]); }
inline void dfs(int u,int fa) {
    pos[++dfs_clock]=u,st[u]=dfs_clock,f[0][u]=fa;
    for (re int i=1;i<=19;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt)
        if (e[i].v!=fa) dfs(e[i].v,u);
    ed[u]=dfs_clock;
}
inline void Build() {
    cnt=n; int tot=0; sort(E+1,E+m+1);
    for (re int i=1;i<=(n<<1);++i) root[i]=i;
    for (re int i=1;i<=m;++i) {
        int u=find(E[i].u),v=find(E[i].v);
        if (u!=v) {
            addEdge(++cnt,u),addEdge(cnt,v);
            root[u]=cnt,root[v]=cnt;
            dis[cnt]=E[i].w,++tot;
        }
        if (tot==n-1) break;
    }
    dfs(cnt,0);
}
inline void insert(int& p,int q,int l,int r,int x) {
    p=++node_tot; t[p]=t[q],++t[p].sum;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[p].lson,t[q].lson,l,mid,x);
    else insert(t[p].rson,t[q].rson,mid+1,r,x);
}
inline int query(int p,int q,int l,int r,int k) {
    if (l==r) return l;
    int mid=(l+r)>>1,num=t[t[p].rson].sum-t[t[q].rson].sum;
    if (num>=k) return query(t[p].rson,t[q].rson,mid+1,r,k);
    else return query(t[p].lson,t[q].lson,l,mid,k-num);
}

int main() {
    n=read(),m=read(),q=read();
    for (re int i=1;i<=n;++i) S[i]=height[i]=read();
    sort(S+1,S+n+1); int s=unique(S+1,S+n+1)-S-1;
    for (re int i=1;i<=n;++i) height[i]=lower_bound(S+1,S+s+1,height[i])-S;
    for (re int i=1;i<=m;++i) E[i].u=read(),E[i].v=read(),E[i].w=read();
    Build();
    for (re int i=1;i<=cnt;++i) {
        if (pos[i]<=n) insert(rt[i],rt[i-1],1,s,height[pos[i]]);
        else rt[i]=rt[i-1];
    }
    int lastans=0;
    while (q--) {
        int v=read(),x=read(),k=read();
         if (lastans!=-1) v^=lastans,x^=lastans,k^=lastans; //Luogu上请去掉这句话
        for (re int i=19;i>=0;--i)
            if (f[i][v]&&dis[f[i][v]]<=x) v=f[i][v];
        if (t[rt[ed[v]]].sum-t[rt[st[v]-1]].sum<k) lastans=-1;
        else lastans=S[query(rt[ed[v]],rt[st[v]-1],1,s,k)];
        printf("%d\n",lastans);
    }
    return 0;
}
最后修改:2019 年 10 月 13 日 05 : 02 PM