双対セグメント木

僕が双対セグメント木だと思ってたもの、半分の遅延セグメント木なのでは

作用が可換だと無意識に前提した実装にしていた

可換でない"上書き作用"の時に正しく動作しない

タイムスタンプを付与することで可換なmax演算に変えた

これが下記に対応するのでは

双対セグメント木

作用が 区間加算・区間chmin のような 作用させる順番を入れ替えても結果が変わらない 作用のとき、作用側を通常のセグメント木のように処理することができ、若干速い

区間代入のやり方

(時間, 代入する値) をペアにして chmax するとできる。