ARC 060 E 高橋君とホテル

• 問題

問題概要

直線上のN個の点x_iが与えられる.
1回に合計距離Lまでの点から点への移動が可能として, 以下のQ個のクエリを処理せよ.
- a,b間の移動には何回移動が必要か
1 <= N <= 10⁵, 1 <= Q <= 10⁵

解法

r[i][k] := (iから2^k回正方向に移動してたどり着ける頂点)
初期化 r[i][0] = (2分探索でx[i]+L以下の最大の点)
遷移 r[i][k+1] = r[r[i][k]][k]
とダブリングで下処理をしておいて,
クエリa,b(a<b)には,kを逆順として
- r[a][k] < b ならr[a][k]に移動 を繰り返す.
計算量はO((N+Q)logN)

メモ

ダブリング全般として,クエリの判定のところで r[a][k] < bは等号がつかないのに引っかかった.
(等号をつけると無駄な回数足してしまう可能性がある)

コード