セグ木に乗っかるモノイド

自由モノイドの商モノイドを乗っけるイメージ。

セグ木を使った問題例

• ABC343 F (1点更新, 区間2番目に大きい値の個数取得)
  • 「2番目に大きい値の個数」だけではモノイド作れない（連結ができない）。他に必要な情報として「最大値」「最大値の個数」「2番目に大きい値」も必要。
    • 必要な情報から膨らませていくイメージ。
• 1点更新のたびに最大の区間和出力
  • 問題文
  • 欲しいのは最大の区間和。ただし、連結のときに「最大の区間和」だけでは情報がたりていない。連結時の最大の区間和を求めるには、prefix_sum_max, suffix_sum_maxもほしい。さらに連結時の prefix_sum_max, suffix_sum_max を求めるときには、ただのsum の情報も必要になる（そういう膨らませをする）
  • ソースコード
• 区間転倒数取得
  • Library Practice Contest L - Lazy Segment Tree
• 平面走査
  • 転倒数の計算
  • ABC351 F - Double Sum
    • 一般に 二重和(2つの値)
• オイラーツアーによるLCA

モノイド も参照

セグ木上の二分探索

数列 $(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