E - 高橋君とホテル
[Q] https://atcoder.jp/contests/arc060/tasks/arc060_c
・解説よくよむ
https://blog.hamayanhamayan.com/entry/2016/09/01/081201
Q. ダブリング？
A. https://algo-logic.info/doubling/
繰り返し二乗法を、開始地点別に記録するようなもの。
DP[2^k日後][i番目の町から] = 移動する町。
DP[0][0] = 0番目の町から2^0日後に到着する町。
DP[2][1] = 1番目の町から2^2日後に到着する町。
DP[10][1] = 1番目の町から2^10日後に到着する町。
のように管理する。
入力例1
9
1 3 6 13 15 18 19 29 31
10
4
ll DP[21][100010]; // DP[2^j日後][i番目の町から]=到達する町
Q. デバッグ？
A. DP[i][j]のindex値を出力。
2 3 4 6 6 6 7 8 8
4 6 6 7 7 7 8 8 8
7 8 8 8 8 8 8 8 8
8 8 8 8 8 8 8 8 8
DP[0][0] = 2 // 0町 の 1日後 は 2町。
DP[1][0] = 4 // 0町 の 2日後 は 4町。
DP[2][0] = 7 // 0町 の 4日後 は 7町。Q. ダブリング入れた後は？
A. bの1日前に到達する場所を目指す。最後に1日増やす。
ll ans = 0;
for(ll k=20; k>=0; --k){
if (DP[k][a]>=b) continue; // 1個前indexまで動く
a = DP[k][a]; // 町を移動する
ans += 1LL<<k; // 2^k日経過させる
}
++ans;実装。
ll DP[21][100010]; // DP[2^j日後][i番目の町から]=到達する町
ll N, L, Q;
void debug(){
rep(i, 21){
rep(j, N) cout << DP[i][j] << " ";
cout << endl;
}
}
int main(){
cincout();
cin >> N;
vector<ll> X(N);
rep(i, N) cin >> X[i];
cin >> L >> Q;
// doubling
rep(i, N){
DP[0][i] = upper_bound(all(X), X[i]+L) - X.begin() - 1; // 次の町のindexを入れる
}
rep(k, 20){
rep(i, N) DP[k+1][i] = DP[k][DP[k][i]];
}
// debug();
rep(i, Q){
ll a, b;
cin >> a >> b;
--a, --b;
if (a>b) swap(a, b);
ll ans = 0;
for(ll k=20; k>=0; --k){
if (DP[k][a]>=b) continue; // bまであと1日でいける町を探す
a = DP[k][a]; // aを移動する
ans += 1LL<<k; // 2^k日経過させる
}
++ans;
cout << ans << endl;
}
}