まず遅延セグメント木を理解してください
http://tsutaj.hatenablog.com/entry/2017/03/30/224339
発祥
https://kimiyuki.net/blog/2019/02/22/dual-segment-tree/
通常、遅延セグメント木は値の配列と遅延の配列を持つが、ここでは値の配列は最下段だけ、遅延の配列は最下段以外を持つ
このとき、区間加算・区間代入・区間chmin などのクエリの場合、作用 2 つをマージする操作と、値に作用を適用する操作が同じであるため、遅延の配列と値の配列をつなげて 1 つの遅延の配列と思うことができて、うれしい。
ここは半分にした遅延セグメント木と同じ
遅延セグメント木は値の配列と遅延の配列を持つが、値の配列は最下段だけ、遅延の配列は最下段以外を持つ
このとき、区間加算・区間代入・区間chmin などのクエリでは、作用 2 つをマージする操作と、値に作用を適用する操作が同一視できるため、遅延の配列と値の配列をつなげて 1 つの遅延の配列と思うことができて、うれしい。
さらに、遅延させたものを下に伝播させる機能を削除する。
その代わり、1 点取得の際に、遅延させたものを上に取りに行く。
こうすると、通常セグ木の区間取得のように区間作用をし、1 点更新のように 1 点取得をするセグ木ができる。
"区間取得のように区間作用をし、1 点更新のように 1 点取得をする" って双対じゃない?
(時間, 代入する値) をペアにして chmax するとできる。