https://atcoder.jp/contests/nikkei2019-final/submissions/15652985
- 累積和にすることで区間和をO(1)で処理できる
- 半開区間で処理することで[l, l+range)の累積和が答えになる
制約から各kの答えを
で処理しなければならない。例えばk=500のとき[0, 500)から[N-500, N)までの区間全て調べないといけないが、全て計算していては各kについて
の計算量になってしまう。累積和を使うことで各区間合計が
で取得できるので、各kの答えをで得ることが出来る。半開区間なので区間右端がNまで許されることに注意する。
