CodeChef: Subtree swapping - pekempey's blog

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)でできる。解析はそこまで難しくないが、面白くもなんともない式変形をするだけなのでここには書かない。

前に似たような問題を見たから解法はすぐに分かった。実装はやや面倒。