考えたこと

クエリが10^5

盤のサイズが90000

要求された数値を盤から探すのに線形オーダーだと間に合わない

定数オーダーでもいやらしい問題として「10^5回、1から90000まで1個ずつ増やす」をやられるとやはり間に合わない

というか数が9万でクエリが10万だから、重なりまくると思った方がいいか

つまりコストを足し合わせるところはキャッシュされるべき

まず線形オーダーで数値から座標への逆写像テーブルを作る

次にDで割った余りごとにD本の累積和を作る

これは逆写像テーブルがあれば線形オーダーになる

ここまで準備すれば1クエリは定数オーダーになる

公式解説OK

ABC089D