読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

ARC 030: D - グラフではない (Left-Leaning Red-Black Tree)

永続平衡二分探索木 Left-leaning Red-Black Tree

LLRB (left-leaning red-black tree) の join/split の情報が少なすぎるのでメモ。問題自体は大分前に解いた。

http://arc030.contest.atcoder.jp/tasks/arc030_4

解法

永続平衡二分探索木を使えばいい。今回は LLRB を実装した。

LLRB というのは赤黒木に黒の右は赤ではないという条件(以下 LL 条件と呼ぶ)を加えたもの。対称性がないので反転機能をつけようと思うと困るのだが、割と簡単に実装できる。といっても普通の赤黒木でもjoin/splitは簡単な気がするが。

普通の赤黒木は以下のスライドを見ると良い。

https://www.ioi-jp.org/camp/2012/2012-sp-tasks/2012-sp-day4-copypaste-slides.pdf

split は LLRB 特有の操作は不要なので、join に関してだけ書いておく。コードを見た方が早い。

node *join_sub(node *x, node *y) {
    if (x->h == y->h) return create(x, y, true);

    // ここはやるだけ
    if (x->h > y->h) {
        x = push(x);
        x->r = join_sub(x->r, y);
    } else {
        y = push(y);
        y->l = join_sub(x, y->l);
        x = y;
    }
    fix(x);

    // 左回転
    if (x->r->c) x = create(create(x->l, x->r->l, true), x->r->r, x->c);

    // 右回転
    if (x->l->c && x->l->l->c) x = create(create(x->l->l, false), create(x->l->r, x->r, false), true);
    return x;
}

node *join(node *x, node *y) {
    // どちらかが null ならもう一方を返せばいい
    if (!x) return y;
    if (!y) return x;

    // 根が赤であるようなものも渡されるので、きちんと黒にしておく(しないとバグる)
    if (x->c) x = create(x, false);
    if (y->c) y = create(y, false);

    // 本格的な join
    x = join_sub(x, y);

    // 根は黒にしておく
    x->c = false;
    return x;
}

自明ではないのは次の部分だろう。

// 左回転
if (x->r->c) x = create(create(x->l, x->r->l, true), x->r->r, x->c);

// 右回転
if (x->l->c && x->l->l->c) x = create(create(x->l->l, false), create(x->l->r, x->r, false), true);

x->r が赤だったら左回転を掛ける。これで LL 条件が満たされる。次に x->lx->l->l が両方赤だったら右回転を掛ける。回転時には適切に色を変える。

これだけで OK。LL 条件のおかげ。push のタイミングもそこまで自明ではないが、注意深く考えるとこれで OK。


1134 ms。RBST に劣らない速度はある。ケースによっては圧倒的に RBST より速い。RBST に比べて join/split が重いんだろうけど、加算/総和は木の高さが低い分高速に動くんだと思う。つまり加算/総和クエリが多いほど有利。

(追記 2016/11/24) 10,000,000ノードから2,000,000ノードの回収に変えたら 897 ms になりました。update/query を split を使って手抜きした実装は 1265 ms でした。速いですね。

参考

Algorithms with Python / 赤黒木 (red-black tree)