きろく

特筆すべき記録のまとめ

全国統一プログラミング王決定戦本戦:D - Deforestation

問題

atcoder.jp

解法

竹を切るとき,最後に切った時刻が分かれば得点が分かる.なので,竹 L_i から竹 R_i の最後に切った時刻の総和を求められれば,各イベントの得点がわかる.最後に切った時刻は区間 [L_i, R_i] ごとに更新されるので,区間更新・区間和取得の遅延セグ木を使うことで O(logN) で両方を行うことが出来る.O(MlogN).

解答

atcoder.jp

f:id:babcs2035:20190328200029p:plain