CodeChef: Subtree swapping
codechef の practice ってあまり使わないので知らなかったんですが、コンテストから practice に問題が公開されるまで大分時間がかかるんですね。復習しづらい。
https://www.codechef.com/problems/SBSWAP
オイラーツアーの切り貼りは、以下の記事で説明しているので、この記事ではそこまで触れません。
HackerRank 101 Hack May 2016: Tree Splitting - pekempeyのブログ
遅延伝播とかも触れないので、詳細はコードを参考にしてください。ライブラリ部が多いですが、main関数を見てれば何となく処理の意味はわかると思います。
解法
オイラーツアーの列を切ったり繋いだりすることで部分木の交換は可能である。切ったり繋いだり、といった操作は平衡二分探索木が得意である。
平衡二分探索木の split といったら、おそらく split(x, k):= 木x を [0,k),[k,n) に分割する
といったものが一般に使われる。
今回はどこのインデックスで切るかが分からないため、これだと扱いにくい。split(x):= ノード x より小さい範囲と大きい範囲で分割する
のような、インデックスではなくノードを分割位置に指定できると良い。
実装方法としては、
- RBSTに
indexOf(x):=ノードxが何番目のノードか?
という機能をつける - スプレー木の splay 操作で根に持ち上げて左の子(あるいは右の子)を切る
- その他
がある。indexOfの実装はそんなに大変ではない。RBSTのノードに親ノードへのポインタを張っておいて、登っていけばいい。登りながら自分より小さいノードの個数が求められて、自分のインデックスが分かる。
解説は以上なので、あとはスプレー木について説明する。
スプレー木
スプレー木で最も重要なのは splay 操作と呼ばれる操作である。splay(x) というのはノード x が木の根になるまで回転操作で持ち上げる操作のことである。つまり splay(x)を呼び出した後、xは木の根になる。
splay 操作を使うことで join/split は容易に実装できる。
join
// x と y は木の根である必要はない。 node *join(node *x, node *y) { if (x == nil) return y; if (y == nil) return x; // x, y を両方木の根にしておく splay(x); splay(y); // xを含む木の最も右にあるノードを見つける。 for (; x->r != nil; x = x->r); // 最も右のノードを根にする。このとき x->r=null である。 splay(x); // 繋ぐ。 x->r = y; y->p = x; return fix(x); }
splitL
// xより左を切り離す node *splitL(node *x) { // xをsplayし、左を切り離す node *c = splay(x)->l; x->l = c->p = nil; fix(x); return c; }
計算量解析
ポテンシャル解析により、splay操作はならしO(log n)でできる。解析はそこまで難しくないが、面白くもなんともない式変形をするだけなのでここには書かない。