ABC089D

https://gyazo.com/a49eb876a37bc8c277e28d5080a06365

考えたこと

クエリが10^5

盤のサイズが90000

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

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

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

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

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

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

公式解説OK