[CF893F] Subtree Minimum Query

Description:

给定一棵树,每次询问某点子树中到其不超过k的所有点的最小点权
强制在线

Hint:

(n,mle 10^5)

Solution:

看到题目第一反应是以深度为下标,dfs序为版本建树

然而不行,因为min不满足前缀可减

所以我们换过来,每个(dep)建树表示(<=dep)所有点的权值

在上面直接查x子树的min就好了

貌似这题用线段树合并就是SBT......

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mxn=5e5+5,inf=1e9;
int n,m,tot,cnt,rk[mxn],hd[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
    t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

int df,dep[mxn],lst[mxn],dfn[mxn],tr[mxn<<5],ls[mxn<<5],rs[mxn<<5],a[mxn],rt[mxn];

void dfs(int u,int fa) {
    dep[u]=dep[fa]+1; dfn[u]=++df;
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa) continue ;
        dfs(v,u);
    }
    lst[u]=df;
}

int cmp(int x,int y) {
    return dep[x]<dep[y];
}

void update(int las,int &p,int l,int r,int pos,int val) {
    p=++tot; 
    if(l==r) {tr[p]=min(tr[p],val);return ; }int mid=(l+r)>>1;
    if(pos<=mid) update(ls[las],ls[p],l,mid,pos,val),rs[p]=rs[las];
    else update(rs[las],rs[p],mid+1,r,pos,val),ls[p]=ls[las];
    tr[p]=min(tr[ls[p]],tr[rs[p]]);
} 

int query(int p,int l,int r,int ql,int qr) {
    if(!p) return inf;
    if(ql<=l&&r<=qr) return tr[p];
    int mid=(l+r)>>1; int res=inf;
    if(ql<=mid) chkmin(res,query(ls[p],l,mid,ql,qr));
    if(qr>mid) chkmin(res,query(rs[p],mid+1,r,ql,qr));
    return res;
}

int r;

int main()
{
    n=read(); r=read(); int u,v,p,q; memset(tr,0x3f,sizeof(tr));
    for(int i=1;i<=n;++i) rk[i]=i,a[i]=read();
    for(int i=1;i<n;++i) {
        u=read(); v=read();
        add(u,v); add(v,u);
    }
    dfs(r,0); int ans=0;
    sort(rk+1,rk+n+1,cmp);
    for(int i=1;i<=n;++i) 
        update(rt[dep[rk[i-1]]],rt[dep[rk[i]]],1,n,dfn[rk[i]],a[rk[i]]);
    m=read();
    for(int i=1;i<=m;++i) {
        p=(read()+ans)%n+1; q=(read()+ans)%n;
        printf("%d
",ans=query(rt[min(dep[p]+q,dep[rk[n]])],1,n,dfn[p],lst[p])); //注意特判深度超出最大深度
    }
    return 0;
}