RBSTの使用例 - ferinの競プロ帳

平衡二分探索木できることが多くてよくわからないのでまとめ

平衡二分探索木についてはプログラミングコンテストでのデータ構造 2 ～平衡二分探索木編～がわかりやすい
平衡二分探索木にモノイドが乗る話については Implicit Treap - 競プロ練習記録がわかりやすい
上記2つはtreapについての話でしたが，RBSTにするときはmergeする方向をランダムに決めるだけで木の高さを期待値で $O(\log N)$ に抑えられるので大体同じです

抽象化の方針

T → 頂点に乗せる型
頂点の値，その頂点を根とする部分木の和についての値を2変数で(val,sumのように)別にもつのではなく，1変数だけ持ちます．valとsumを別の型にしたいときがあったので，val一つだけでTのメンバ変数に頂点の値と部分木の和の両方を持たせるようにしました．
E → 遅延用の型
f(T, T, T) → 左の部分木，頂点自身，右の部分木の値を渡し，マージするための関数
g(T, E, int) → T に E を作用させる．部分木のサイズに応じて処理が変わるときのために要素数を渡します．
h(E, E) → E のマージ

reverseあるのに非可換な演算用の反転わたしてないのに今気づいた
あと各頂点に親へのポインタをもたせて根を $O(\log N)$ で求められるようにしました

merge-splitベースのRBSTにモノイドを乗せた実装
program_contest_library | 競技プログラミングのライブラリ

仮想配列として扱う

二分探索木というと順序付き集合を管理するデータ構造として使われることが多い(要出典)ですが，配列のように扱うこともできます．要素の大小をkeyにするのではなく，数列のindexをkeyとして並べます．つまり，木の形に配列を当てはめます．

RBSTでは merge, split, insert, erase や $k$ 番目の要素へのアクセスが $O(\log N)$ で可能なので，普通の配列では $O(N)$ かかってしまうような操作が $O(\log N)$ で可能な配列のように扱えます．

モノイドが乗るのでセグ木と同様に，区間クエリなどについても $O(\log N)$ で行うことができます．区間 $\lbrack l,r)$ に演算を行いたい場合，split で区間 $\lbrack l,r)$ を取り出して，その木の根のlazyに演算をすればよいです．別の頂点とmergeを行う場合は，子をつなげる前に適切にevalすることでちゃんと遅延伝播できます．

順序付き集合として扱う

STLのsetやmapではk番目の要素を求めることができませんが，平衡二分探索木を順にたどっていくことで $O(\log N)$ で求められます．モノイドを乗せることで上位 $k$ 個の演算結果などを取得することもできます．

問題例

いつものverify用問題列に対するクエリ
DSL_2_A
DSL_2_B
DSL_2_F
DSL_2_G
DSL_2_H
DSL_2_I

AOJ1508 RMQ

点更新，巡回シフト，最小値を求めるクエリを高速に処理してくださいという問題

点更新 → $k$ 番目へのアクセスは $O(\log N)$ です
巡回シフト → merge と split を使って， $l$ 番目が $\lbrack l+1,r \rbrack$ の後ろになるようにつなぎかえます
最小値 → モノイドとして min を乗せればよいです

提出

B - カッコつけ

消すべき文字は，余っている'('と途中の累積和が負になっているような')'です．( と ) を +1 と -1 に置き換えて累積和を取ります．カッコ悪さは，(累積和) - 2*(累積和のmin) で求められます．

+1 or -1，累積和，累積和のmin を各頂点について保持しつつ，insertやeraseが高速にできれば解けます．この値は RBST に載せられます．

提出

E - Black Cats Deployment

辺が無い状態からはじめて，重みが大きい辺から順番に追加していきます．この辺 $(u,v)$ が答えに寄与する分を考えると，

$u$ が属する連結成分の頂点に， $(v$ が属する連結成分の要素数 $) \times ($ 辺の重み $)$ を一様加算
$v$ が属する連結成分の頂点に， $(u$ が属する連結成分の要素数 $) \times ($ 辺の重み $)$ を一様加算

を行いたいです．連結成分の要素数はunionfind等で求められます．残りの辺の追加と連結成分に対する加算をRBSTを用いて実現します．

辺の追加： mergeでできます
連結成分の頂点に対して一様加算：頂点が属する木の根のlazyに加算

提出

H - 救援

クエリを順に見ていきます．そもそも連結な集合を結ぶ場合，答えは変化しないので前のクエリと同じ答えを出力します．新たに連結した集合以外の頂点の部分は変化しません．したがって，新たに連結した集合に関してのみ，答えがどのように変化したか考えます．

頂点の連結性についてはUnionFind等を使えば管理できます． $p$ が大きい方から並べる順序付き集合とxの和を各連結成分に持たせます．支援は $p$ が大きい国から貪欲に割り当てればよいです． $p$ について降順に並べたときの先頭何個かについて $x$ や $px$ の和が取得できれば，連結成分ごとに答えを求められます．RBSTにモノイドとして和を乗せることでこれは求められます．

あとは各クエリで集合のマージが必要ですが，これはマージテクで高速にできるのでこの問題は解けました．

これ昔書いたやつなのでライブラリが古い
提出