(Sub) tree を区間で表す．
Pre order P : \( [r \ (A_{0})(A_{1})] \),
In order I: \( [(B_{0})\ r \ (B_{1})] \)
の形で表せる．ここで， \(r\) は root, \(A_{0}, B_{0}\) は左側の subtree, \(A_{1}, B_{1}\) は右側の subtree. Root \(r\) の入る場所以外は同じ．
\(P\) の方を見れば，root \(r\) の位置はすぐに分かる． ここで， \(I\) における \(r\) の位置を取得すれば， \(I\) を \(r\) で左右に分けて， \(r\) の左右の subtree に対応する区間が分かる． とくに，それぞれの subtree の頂点の個数が分かる．
よって，その個数を \(x,y\) とおけば その \(P\) を \(x,y\) を用いて分割できる． 分割した \(P\) における区間が subtree になるので，これを再帰的に繰り返す． 構成と同時に判定ができる．
実装
再帰関数の戻り値 in int は，
- -1 : 条件を満たさない
- 0 : subtree が empty
- a (>0) : (調べている subtree の root) + 1
としている．
メモ
\(P,I\) の subtree の長さは等しいことをキープしながら遷移するので， 再帰関数の引数は \(P\)における左端， \(I\)における左端， 長さ の 3つで十分． 引数の個数を減らせれば，ミスも少なくなる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
//---------------------------------------------------------------------------------------------------
int main() {
ll n, m ;
cin >> n;
vll po(n), io(n);
cinv(po); cinv(io);
vll v(n);
rep(i,n){
po[i]--;
io[i]--;
v[io[i]] = i;
}
// return
// -1 : fail
// 0 : empty tree
// greater than 0 : the index of root (1-ind)
auto f = [&](auto f, ll lp, ll li, ll n) -> int {
if(n == 0) return 0;
ll s = po[lp]; // root
ll i = v[s];
if(!in(i, li, li+n)) return -1;
ll ls = i - li;
ll rs = n-(ls+1);
l[s] = f(f, lp+1, li, ls);
r[s] = f(f, lp+1+ls, li+1+ls, rs);
if(l[s] == -1 || r[s] == -1) return -1;
return s+1;
};
if(f(f,0,0,n) != 1){
cout << -1 << endl;
}else{
rep(i,n){
cout << l[i] << " " << r[i] << endl;
}
}
return 0;
}
