题意

给定一棵树和根，每个点有点权，强制在线询问\(x\)子树里离\(x\)距离不超过\(k\)的最小点权。

分析

权值线段树合并的套路题，dfs，以深度作为下标，点权作为值，对每个点建立一颗权值线段树，然后回溯的时候合并到父节点的线段树上。
合并时维护最小值，查询时也是查询区间最小值。
内存给得多的情况下数组往死里开，不要白白送一发RE。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=6e5+50;

const int INF=0x3f3f3f3f;

vector<int> g[N];

int a[N],n,rt,u,v,lst,q,x,k;

int mn[N*30],ls[N*30],rs[N*30],tot,dep[N],tr[N];

void insert(int &rt,int l,int r,int p,int v){

    if(!rt){

        rt=++tot;

    }

    mn[rt]=v;

    int mid=(l+r)/2;

    if(l<r){

        if(p<=mid){

            insert(ls[rt],l,mid,p,v);

        }else{

            insert(rs[rt],mid+1,r,p,v);

        }

    }

}

int merge(int a,int b){

    if(!a || !b){

        return a+b;

    }

    int rt=++tot;

    mn[rt]=min(mn[a],mn[b]);

    ls[rt]=merge(ls[a],ls[b]);

    rs[rt]=merge(rs[a],rs[b]);

    return rt;

}

int query(int rt,int l,int r,int ql,int qr){

    if(!rt){

        return INF;

    }

    if(ql<=l && qr>=r){

        return mn[rt];

    }

    int ans=INF;

    int mid=(l+r)/2;

    if(ql<=mid){

        ans=min(ans,query(ls[rt],l,mid,ql,qr));

    }

    if(qr>mid){

        ans=min(ans,query(rs[rt],mid+1,r,ql,qr));

    }

    return ans;

}

void debug(int rt,int l,int r){

    printf("%d %d %d\n",l,r,mn[rt]);

    if(l==r){

        return;

    }

    int mid=(l+r)/2;

    debug(ls[rt],l,mid);

    debug(rs[rt],mid+1,r);

}

void dfs(int u,int f){

    dep[u]=dep[f]+1;

    insert(tr[u],1,n,dep[u],a[u]);

    int siz=g[u].size();

    for(int i=0;i<siz;i++){

        int v=g[u][i];

        if(v==f){

            continue;

        }

        dfs(v,u);

        tr[u]=merge(tr[u],tr[v]);

    }

}

int solve(int x,int k){

    return query(tr[x],1,n,dep[x],dep[x]+k);

}

int main(){

//    freopen("in.txt","r",stdin);

    scanf("%d%d",&n,&rt);

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

        scanf("%d",&a[i]);

    }

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

        scanf("%d%d",&u,&v);

        g[u].push_back(v);

        g[v].push_back(u);

    }

    dfs(rt,0);

    scanf("%d",&q);

    while(q--){

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

        x=(x+lst)%n+1;

        k=(k+lst)%n;

        printf("%d\n",lst=solve(x,k));

    }

    return 0;

}

巴特西

Codeforces893F_Subtree Minimum Query

题意

分析

代码

最新文章

热门文章