codeforces 893F - Physical Education Lessons 动态开点线段树合并

时间：2023-03-08 15:56:15
codeforces 893F - Physical Education Lessons 动态开点线段树合并

https://codeforces.com/contest/893/problem/F

题意:

　　给一个有根树,

　　多次查询,每次查询对于$x$i点的子树中,距离$x$小于等于$k$的所有点中权值最小的一个

　　查询强制在线

题解:

　　显然,暴力就是,对于每次搜索深搜距离x小于$k$的所有点搜索

　　那么我们考虑优化

　　首先,查询对$x$距离小于$k$的所有点,等价于在整颗树上,查询$\forall dep(x)≤dep(i)≤dep(x)+k$中,在$x$子树中的点的最小值

　　那么,一个大胆的想法就是,对于每个点,用深度去维护区间$[1,n]$,区间信息则为x的子树中,深度$[l,r]$中节点的最小值

　　显然,每个点如果真的开了一个线段树,有两个问题

　　1.空间是$O(n^2logn)$

　　2.时间是$O(n^2logn)$

　　但显然的,本题的询问一定程度上,满足区间加法

　　或者说,其父亲的信息为其子树信息的"和",

　　那么我们可以用动态开点线段树+线段树合并的方式

　   而对于任意的合法询问,动态开点线段树中,也一定在建树的过程中被建立过了(儿子被合并到父亲中了)

　　空间复杂度降低到$O(nlogn^2)$,时间复杂度降低到$O(nlogn)$

　　codeforces 893F - Physical Education Lessons 动态开点线段树合并

#include <bits/stdc++.h>

#define endl '\n'

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)

using namespace std;

int casn,n,m,k;

const int maxn=1e5+7,maxm=1e7+7;

const ll INF=0x3f3f3f3f3f3f3f;

class graph{public:

  struct edge{

    int from,to;ll cost;

    edge(int a,int b,ll c){from=a,to=b,cost=c;}

  };

  vector<vector<edge>> node;

  int ud=0;

  graph(int n=maxn,int f=0){node.resize(n+2);ud=f;}

  void add(int a,int b,int c=1){node[a].emplace_back(a,b,c);if(ud)node[b].emplace_back(b,a,c);}

};

class dsegtree{public:

#define nd  node[now]

#define ndl node[node[now].son[0]]

#define ndr node[node[now].son[1]]

  struct dsegnode {

    int son[2];ll val;

    dsegnode(){val=INF;}

    dsegnode(int x){son[0]=son[1]=0;}

    void update(ll x){val=x;}

  };

  vector<dsegnode> node;

  vector<int> root;

  int cnt,n,s,t,pos;

  dsegtree(int nn,int size=maxm){

    n=nn,cnt=0;

    node.resize(size);

    root.resize(n+2);

  }

  void pushup(int now){nd.val=min(ndl.val,ndr.val);}

  void pushdown(int now){}

  void change(int p,ll x,int now){

    pos=p;

    if(!root[now]) root[now]=++cnt;

    update(1,n,x,root[now]);

  }

  void update(int l,int r,ll x,int now){

    if(pos>r||pos<l) return ;

    if(l==r){

      nd.update(x);

      return ;

    }

    if(!nd.son[0]) nd.son[0]=++cnt;

    if(!nd.son[1]) nd.son[1]=++cnt;

    pushdown(now);

    update(l,(l+r)>>1,x,nd.son[0]);

    update(((l+r)>>1)+1,r,x,nd.son[1]);

    pushup(now);

  }

  void unite(int a,int b){root[a]=merge(root[a],root[b]);}

  int merge(int a,int b){

    if(!a||!b) return a^b;

    int now=++cnt;

    nd.son[0]=merge(node[a].son[0],node[b].son[0]);

    nd.son[1]=merge(node[a].son[1],node[b].son[1]);

    nd.val=min(node[a].val,node[b].val);

    return now;

  }

  ll query(int ss,int tt,int now){s=ss,t=tt;return count(1,n,root[now]);}

  ll count(int l,int r,int now){

    if(s>r||t<l) return INF;

    if(s<=l&&t>=r) return nd.val;

    return min(count(l,(l+r)>>1,nd.son[0]),count(((l+r)>>1)+1,r,nd.son[1]));

  }

};

int main() {

  IO;

  ll n,m,root;

  cin>>n>>root;

  vector<int> dep(n+7,0);

  vector<ll> val(n+7);

  rep(i,1,n) cin>>val[i];

  graph g(n,1);

  register ll a,b;

  rep(i,2,n){

    cin>>a>>b;

    g.add(a,b);

  }

  dsegtree tree(n);

  auto dfs=[&tree,&g,&val,&dep](auto &&dfs,int now,int pre=-1,int dis=1)->void{

    dep[now]=dis;

    tree.change(dis,val[now],now);

    for(auto &i:g.node[now]){

      if(i.to==pre) continue;

      dfs(dfs,i.to,now,dis+1);

      tree.unite(now,i.to);

    }

  };

  dfs(dfs,root);

  cin>>m;

  ll x=0,last=0,k=0;

  while(m--){

    cin>>a>>b;

    x=(a+last)%n+1,k=(b+last)%n;

    last=tree.query(dep[x],dep[x]+k,x);

    cout<<last<<endl;

  }

  return 0;

}

相关文章