2019-03-28 全国統一プログラミング王決定戦本戦:D - Deforestation 競技プログラミング AtCoder 500 点問題 問題 解法 解答 問題 atcoder.jp 解法 竹を切るとき,最後に切った時刻が分かれば得点が分かる.なので,竹 L_i から竹 R_i の最後に切った時刻の総和を求められれば,各イベントの得点がわかる.最後に切った時刻は区間 [L_i, R_i] ごとに更新されるので,区間更新・区間和取得の遅延セグ木を使うことで O(logN) で両方を行うことが出来る.O(MlogN). 解答 atcoder.jp