競プロ AtCoder 4問 切り取り線 (12) (2014本選) 割と綺麗にかけて楽だと思う。segment treeの変な応用はいろいろあるが、これもなかなかに応用しまくっている。最近のやたらとモノイドで貼るだけってのと比べてデータ構造のマージなどをsegtree化するものは…