P7834 [ONTAK2010] Peaks 加强版

· · 题解

传送门

题目大意

感觉题目描述已经足够清楚了。

Solution

这道题需要的东西有点多，我们不妨先来分解一下题目的需求。

马上想到最小生成树，很明显了，和货车运输一样。不赘述了。

好的，又是裸的静态区间第 k 大。由于是强制在线，所以一发主席树就结束了。

好接下来我们把这两个玩意儿结合一下，哦，然后我们掏出一个克鲁斯卡尔重构树就做完了。

我是 fyy，我一眼秒了，感觉这题没啥技巧啊。

好的我具体讲一下。我们对于图做一次重构树，然后在大法师的时候顺便记一下每个节点子树中涵盖的叶节点的 dfn 区间，并据此建主席树，然后直接回答询问就可以了，还是比较模板的，注意细节就可以了。

Code

#include<bits/stdc++.h>
#define ll long long
#define inf (1<<30)
#define INF (1ll<<60)
using namespace std;
const int MAXN=3e6+10;
struct Tree{
    int l,r,ls,rs;
    int sum;
}tr[MAXN];
int ntot,T[MAXN];
int build(int l,int r){
    int i=++ntot;
    tr[i].l=l;tr[i].r=r;
    if(l==r) return i;
    int mid=l+r>>1;
    tr[i].ls=build(l,mid);
    tr[i].rs=build(mid+1,r);
    return i;
}
int upd(int pre,int x){
    int i=++ntot;
    tr[i]=tr[pre];tr[i].sum++;
    if(tr[i].l==tr[i].r) return i;
    int mid=tr[i].l+tr[i].r>>1;
    if(x<=mid) tr[i].ls=upd(tr[pre].ls,x);
    else tr[i].rs=upd(tr[pre].rs,x);
    return i;
}
int query(int L,int R,int k){
    if(tr[L].l==tr[L].r) return tr[L].l;
    int dif=tr[tr[R].ls].sum-tr[tr[L].ls].sum;
    if(k<=dif) return query(tr[L].ls,tr[R].ls,k);
    else return query(tr[L].rs,tr[R].rs,k-dif);
}//主席树求区间第 k 小
struct Edge{
    int x,y,w;
    void input(){
        scanf("%d%d%d",&x,&y,&w);
    }bool friend operator<(Edge a,Edge b){
        return a.w<b.w;
    }
}E[MAXN];
int to[MAXN],head[MAXN],nxt[MAXN],edgec;
void add(int u,int v){
    to[++edgec]=v;
    nxt[edgec]=head[u];
    head[u]=edgec;
}
int f[MAXN],h[MAXN],lsh[MAXN],val[MAXN],num;
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
int fa[MAXN][20],lb[MAXN],rb[MAXN],tot;
void dfs(int x,int fat){
    fa[x][0]=fat;
    for(int i=1;i<20;i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    lb[x]=tot;
    if(head[x]==-1){
        lb[x]=tot;rb[x]=++tot;//包含子节点的区间，注意是左开右闭的
        T[tot]=upd(T[tot-1],lower_bound(lsh+1,lsh+1+num,h[x])-lsh);
        return;
    }
    for(int i=head[x];~i;i=nxt[i])
        dfs(to[i],x);
    rb[x]=tot;
}
int main()
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&h[i]),lsh[i]=h[i];
    sort(lsh+1,lsh+1+n);
    num=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=m;i++)
        E[i].input();
    sort(E+1,E+1+m);
    for(int i=1;i<=n+m;i++)
        f[i]=i;
    int cnt=n;
    memset(val,0,sizeof(val));
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++){
        int fx=find(E[i].x),fy=find(E[i].y);
        if(fx==fy) continue;
        f[fx]=f[fy]=++cnt;
        add(cnt,fx);add(cnt,fy);
        val[cnt]=E[i].w;
    }T[0]=build(1,num);
    dfs(cnt,0);
    int lastans=0; val[0]=0x3f3f3f3f;
    for(int _=1;_<=q;_++){
        int v,x,k;
        scanf("%d%d%d",&v,&x,&k);
        v=(v^lastans)%n+1;k=(k^lastans)%n+1;
        x=x^lastans;
        for(int i=19;i>=0;i--)
            if(fa[v][i]&&val[fa[v][i]]<=x)
                v=fa[v][i];
        int l=lb[v],r=rb[v];
        if(r-l<k) puts("-1"),lastans=0;
        else printf("%d\n",lastans=lsh[query(T[l],T[r],r-l-k+1)]);//求第 k 大，就是求第 len-k 小
    }
}

End