D - Practical Skill Test
- 考えたこと
- クエリが10
- 盤のサイズが90000
- 要求された数値を盤から探すのに線形オーダーだと間に合わない
- 定数オーダーでもいやらしい問題として「10^5回、1から90000まで1個ずつ増やす」をやられるとやはり間に合わない
- というか数が9万でクエリが10万だから、重なりまくると思った方がいいか
- つまりコストを足し合わせるところはキャッシュされるべき
- まず線形オーダーで数値から座標への逆写像テーブルを作る
- 次にDで割った余りごとにD本の累積和を作る
- ここまで準備すれば1クエリは定数オーダーになる
- 公式解説OK
ABC089D