P13840 杏酥桐 题解

· · 题解

手玩一下可以发现，难点在于支持“在一个子树内找到 dfs 序排名为 k 的元素”操作的同时，支持往某个结点下挂一个新的结点。

这个东西可以先离线所有询问，倒着扫询问把树建出来，再正着扫，每次往数据结构里面加入一个 dfs 序上的单点，同时需要查排名和给定排名查对应值的操作（找到 dfs 序位于区间 [l,r] 内、已经被加入数据结构的点中排名为 k 的点）。用 pbds tree 实现，时间复杂度 O(n\log n)。

放代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpi;
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int id,t; cin>>id>>t;
  while(t--){
    int q,n=1; cin>>q;
    vector<vector<int> > g(n);
    vector<int> fa(n,-1),l(n,-1);
    vector<tpi> opr(q);
    for(auto &e:opr){
      int op,u,x; cin>>op>>u>>x,u--;
      if(op==1){
        g[u].emplace_back(-1);
        l.emplace_back(-1);
        fa.emplace_back(u);
        g.emplace_back(),n++;
      }
      e=make_tuple(op,u,x);
    } // 输入询问，预处理必要的信息
    reverse(opr.begin(),opr.end());
    vector<ordered_set> gt(n);
    for(int i=0;i<n;i++)
      for(int j=0;j<g[i].size();j++)
        gt[i].insert(j);
    vector<int> id(n,-1);
    int o=0,pt=n;
    for(auto e:opr){
      int op,u,x; tie(op,u,x)=e;
      if(op==1){
        auto it=gt[u].find_by_order(x);
        pt--,g[u][id[pt]=*it]=pt,gt[u].erase(it);
      }
    } // 倒着扫建树
    reverse(opr.begin(),opr.end());
    vector<int> d(n),e(n,1),mp(n);
    auto dfs=[&](auto &&self,int u)->void{
      mp[d[u]=o++]=u;
      for(int i:g[u])
        if(i!=fa[u])self(self,i),e[u]+=e[i];
    };
    dfs(dfs,0);
    vector<set<pii> > g2(n);
    ordered_set ds;
    for(auto w:opr){
      int op,u,x; tie(op,u,x)=w;
      if(op==1){
        int v=pt++;
        auto it=g2[u].emplace(id[v],v).first;
        if(it!=g2[u].begin())l[v]=prev(it)->second;
        if(next(it)!=g2[u].end())l[next(it)->second]=v;
        ds.insert(d[v]);
      } // 加点
      else{
        if(l[u]<0)cout<<fa[u]+1<<'\n';
        else{
          u=l[u];
          int l=ds.order_of_key(d[u]),r=ds.order_of_key(d[u]+e[u])-1;
          cout<<mp[*ds.find_by_order(min(l+x-1,r))]+1<<'\n';
        } // 查排名
      }
    } // 正着扫回答询问
  }
  return 0;
}