ARC 030: D - グラフではない (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->l と x->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 でした。速いですね。
