ABC258 E - Packing Potatoes (500)
$ 10^{12}個先の結果を順に調べるわけにはいかないのでダブリングで求める
それぞれのじゃがいもから開始したときに次の箱がどのジャガイモから始まるかを求めておく
ジャガイモの重さの累積和を求めておくと二分探索で求めることができる
この情報を使ってダブリングで解く
この構成をする際、重さの合計も情報として持っておく
各クエリで以下を行う
$ k_i番目までの重さの和から$ K_{i-1}番目までの重さの和を引いた値を出力
$ \mathcal{O}((N+Q)\log \max K)
解説の通りサイクルで考えるとダブリングが不要で$ \mathcal{O}(N+Q)