遅延セグ木入門メモ
ゴール：ACLの遅延セグ木を使ってABCの後半を通す
前提：ACLのセグ木は何となく使える。遅延セグ木は区間更新が高速らしいことは知っている。
ステップ1_気持ちの理解
写経して自作のセグ木でAOJを通す。
セグ木の実装がまだ分からなければ木マスター養成講座も観るといいかも。遅延セグ木はないけど双対セグ木はある。 写経して自作の遅延セグ木でAOJを通す。
この記事で伝搬を遅延すると区間更新が高速になる理屈が分からなかったら、分かるまで別の記事を読む。
ステップ2_ACLの遅延セグ木の使い方に慣れる
を読みながら、
AOJのコースの（遅延）セグ木貼るだけっぽい問題をACLで全部通す。AOJでACLは使えないので、ACLの中身から ・segtree.hpp
・lazysegtree.hpp
・internal_bit.hpp
を持ってきて貼る。
ステップ3_ABCの遅延セグ木典型を解く
区間アフィン変換は遅延セグ木に乗る。
遅延セグ木に乗るもの、乗らないもの
区間chminとかは乗らない（Segment Tree Beatsでできる）