この問題は座標圧縮＋遅延セグメント木で解けます。

ノードは「対応する区間で1日に増える実の個数」と「対応する区間ですでに収穫された実の個数」を持ちます。作用素は「最後に収穫が行われた日付」を持ちます。

クエリに対する答えは、「1日で増える個数×収穫日の日付－すでに収穫された個数」となります。

座標圧縮により残る座標は \(O(Q)\) 個であるため、全体で \(O(Q\log Q)\) で解けます。

実装例(C++)

実装上は、作用素の集合がモノイドとなるように、恒等写像の扱いに注意してください。