[CCPC2024 哈尔滨站] 造计算机 题解

· · 题解

有一种非常简洁、没任何细节的做法。

一种暴力是建出类似 01-Trie 的结构，但显然这样点数会过多。

观察到问题在于有大量的结构为满二叉树的重复子树，考虑可持久化数据结构的思想，假设某一棵满二叉树子树在之前出现过（单看这棵子树，对应的值域一定是一个 [0,x)），直接连到那棵子树上面就行。

这样点数和边数的量级是 O(\log R) 的，由于限制很宽松，故可以轻松地通过。

注意处理一下前导 0 的问题。就是从根出发权值为 0 的边缩起来就行。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int V=1<<20;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int L,R; cin>>L>>R;
  vector<int> vt(V,-1);
  vector<vector<pair<int,int> > > g;
  auto new_node=[&](){
    g.emplace_back();
    return g.size()-1;
  }; // 新建一个点
  auto dfs=[&](auto &&self,int l,int r,int ql,int qr,int x=-1)->int{
    if(x<0&&l==ql&&r==qr&&!ql&&~vt[qr])return vt[qr];
    // 重复子树，直接取之前的结果
    int m=l+r>>1,u=~x?x:new_node();
    if(ql<=m){
      int w=self(self,0,m-l,ql-l,min(qr,m)-l,u?-1:u);
      if(u)g[u].emplace_back(w,0);
    } // 左边有
    if(qr>m){
      int w=self(self,0,r-(m+1),max(ql,m+1)-(m+1),qr-(m+1));
      g[u].emplace_back(w,1);
    } // 右边有
    if(l==ql&&r==qr)vt[r]=u; // 结果存下来
    return u;
  };
  new_node(),new_node(),vt[0]=1,dfs(dfs,0,V-1,L,R,0);
  cout<<g.size()<<endl;
  for(int u=0;u<g.size();u++){
    cout<<g[u].size()<<' ';
    for(auto [v,w]:g[u])
      cout<<v+1<<' '<<w<<' ';
    cout<<'\n';
  }
  return 0;
}