この問題はかなり苦労しました。というのも、動的SegmentTreeで解こうとすると空間計算量が非常に厳しくなるからです。 ですが、よく考えると動的SegmentTreeの空間計算量がO(log|区間の幅|)というのは変な気がします。なので少し考えてみたら、平衡二分木を…