Quiz
https://codeforces.com/contest/1189/problem/C
AC Code
https://codeforces.com/contest/1189/submission/56582743
観察
- クエリ数が多いので、1クエリあたりO(1), O(logN)あたりで解かないと間に合わない
- 愚直にシミュレーションしたら間に合わない
- 途中の結果は不要で、最後の結果だけ欲しい
- シミュレーションしたとして、どこかの段階で左右の和が10を超えたらキャンディが＋１
- その時、全体からは、数字が10減る
解法
- 範囲和 / 10 が答え
- 範囲和は累積和を持っておけばO(1)で求まる
ポイント
- 最後の結果だけが欲しい場合、初期状態のみからO(1)で求まることがある
