セグ木に乗っかるモノイド
自由モノイドの商モノイドを乗っけるイメージ。
セグ木に乗っけるモノイドの代表例
セグ木テク
セグ木上の二分探索
数列 $(a_0, \ldots, a_{n-1})$ をセグ木で管理している状態を考える
- 述語関数について
- 単位元が true になるように述語関数を作る
- ある種の単調性を満たすように設計をする
- 長さ0の総積(単位元)は true で、数列の長さが長くなるほど false になりやすい感じにする？
max_right(l, p)
- left $l$ を固定して、$p(\prod_{i \in [l, r)} a_i) = \mathrm{true}$ となるような最大の $r$ を求める
- 区間の始点を固定したとき、どこまで終点を右に伸ばせるか
- めぐる式二分探索でいうと、ok が $l$ で ng が $n+1$ というノリ。
min_left(r, p)
- right $r$ を固定して、$p(\prod_{i\in[l, r)} a_i) = \mathrm{true}$ となるような最小の $l$ を求める
- 区間の終点を固定したとき、どこまで始点を左に伸ばせるか
- めぐる式二分探索でいうと、ok が $r$ で ng が $-1$ というノリ。
- ドキュメント: https://atcoder.github.io/ac-library/production/document_ja/segtree.html
- 内部挙動: tbw
- 応用例