競プロ用ライブラリを作る Advent Calendar 2024の9日目です.
RangeSet って?
競プロをやっていると時々, 集合をいくつかの区間の組み合わせで表現したくなる時があります.
ということで集合をいくつかの区間の組み合わせで表現するデータ構造を今RangeSetと名付けました. これを実装します.
仕組み
色々考えた結果,「区間の境界を昇順に並べた配列$a = [a_1,a_2,...,a_N]$」と「無限小を含むフラグ$f$(0 or 1)」の組でやるのが一番簡潔そうだという結論に至りました. この組が表す集合を, 以下$S(a, f)$と書くことにします.
$S(a, f)$は「$a_i\le x$になる$a_i$の個数$+f$が奇数のとき, かつそのときに限り$x\in S(a, f)$」という集合です. 表現を変えると
- $f = 0$ のとき, $S(a, f) = \left[a_1,a_2\right)\cup\left[a_3,a_4\right)\cup\left[a_5,a_6\right)\cup\cdots$
- $f = 1$ のとき, $S(a, f) = \left(-\infty,a_1\right)\cup\left[a_2,a_3\right)\cup\left[a_4,a_5\right)\cup\cdots$
という感じです. どちらも$a$が区間の境界を昇順に並べたようになってますね.
それと, 区間に$a$の要素を2つずつ割り当てると偶奇によっては1余りますが, そういう場合は$\cdots\cup\left[a_{N-2},a_{N-1}\right)\cup\left[a_N,\infty\right)$みたいな感じの集合を表しているとします.
この集合の演算ですが, まず$S(a, 0)$と$S(a, 1)$は補集合になってるので, $f$を切り替えれば補集合が$O(1)$で求められます.
和集合, 積集合, 排他的和集合を実装します. 2つの集合と論理演算$\star$を使って$S(c, h) = \set{x: (x\in S(a, f)) \star (x\in S(b, g))}$という集合を新しく作りましょう. 以下のようにします.
- $h = f \star g$になる
- $c$を空の配列で初期化する
- $a, b$の値を小さいほうから順に出して(以下, その値を$x$), 順に次のことをする
- $x\in a$なら$f$を反転する
- $x\in b$なら$g$を反転する
- 上の2つの操作を行った結果$f\star g$の値が切り替わったなら, $c$に$x$を追加する
これを共通化してしまえばあとは楽です.
Rustではイテレータよりも高階関数で実装した方が簡単なのでそうしましょう.
実装
上で書いたことをそのまま実装しただけです.
Rustはコピーを行わずに「配列の値を小さいほうから順に出す」を実装するのがだいぶ重いです. 頑張りましょう.
まとめ
いかがでしたか?
明日は乱択なやつを実装します.