AtCoder Regular Contest 060 E - 高橋君とホテルTak and Hotels（倍增）

E - 高橋君とホテル / Tak and Hotels

---

Time Limit: 3 sec / Memory Limit: 256 MB

Score : 700700 points

Problem Statement

NN hotels are located on a straight line. The coordinate of the ii-th hotel (1≤i≤N)(1≤i≤N) is xixi.

Tak the traveler has the following two personal principles:

He never travels a distance of more than LL in a single day.He never sleeps in the open. That is, he must stay at a hotel at the end of a day.

You are given QQ queries. The jj-th (1≤j≤Q)(1≤j≤Q) query is described by two distinct integers ajaj and bjbj. For each query, find the minimum number of days that Tak needs to travel from the ajaj-th hotel to the bjbj-th hotel following his principles. It is guaranteed that he can always travel from the ajaj-th hotel to the bjbj-th hotel, in any given input.

Constraints

2≤N≤1052≤N≤1051≤L≤1091≤L≤1091≤Q≤1051≤Q≤1051≤xi<x2<...<xN≤1091≤xi<x2<...<xN≤109xi+1−xi≤Lxi+1−xi≤L1≤aj,bj≤N1≤aj,bj≤Naj≠bjaj≠bjN,L,Q,xi,aj,bjN,L,Q,xi,aj,bj are integers.

Partial Score

200200 points will be awarded for passing the test set satisfying N≤103N≤103 and Q≤103Q≤103.

---

Input

The input is given from Standard Input in the following format:

NN x1x1 x2x2 ...... xNxN LL QQ a1a1 b1b1 a2a2 b2b2 : aQaQ bQbQ

Output

Print QQ lines. The jj-th line (1≤j≤Q)(1≤j≤Q) should contain the minimum number of days that Tak needs to travel from the ajaj-th hotel to the bjbj-th hotel.

---

Sample Input 1 Copy

Copy

9 1 3 6 13 15 18 19 29 31 10 4 1 8 7 3 6 7 8 5

Sample Output 1 Copy

Copy

4 2 1 2

For the 11-st query, he can travel from the 11-st hotel to the 88-th hotel in 44 days, as follows:

Day 11: Travel from the 11-st hotel to the 22-nd hotel. The distance traveled is 22.Day 22: Travel from the 22-nd hotel to the 44-th hotel. The distance traveled is 1010.Day 33: Travel from the 44-th hotel to the 77-th hotel. The distance traveled is 66.Day 44: Travel from the 77-th hotel to the 88-th hotel. The distance traveled is 1010.

题意：

给你x轴上n(n<=1e5)个点的坐标a[i](0<a[i]<a[i+1]<...<=1e9)，给你一个数l表示每次最多走长度l，且只能走到给你的点上。(a[i+1]-a[i]<=l)

Q次询问，每次询问两个点x,y，问从x走到y最少需要多少步。

思路：

直接倍增，预处理每个点能走的最远的点。

每次查询直接跳就行。

代码：

#include<bits/stdc++.h> #define ll long long #define inf 0x3f3f3f3f #define rep(i,a,b) for(register int i=(a);i<=(b);i++) #define dep(i,a,b) for(register int i=(a);i>=(b);i--) using namespace std; const int maxn=2e5+5; //const double pi=acos(-1.0); //const double eps=1e-9; //const ll mo=1e9+7; int n,m,k,l,q; int a[maxn],c[maxn]; int f[maxn][25]; int ans,tmp,cnt; int flag; char s[maxn]; bool ok[maxn]; int main() { int T,cas=1; //scanf("%d",&T); while(scanf("%d",&n)!=EOF) { rep(i,0,n) c[i]=1; int j=1; rep(i,1,n) scanf("%d",&a[i]); scanf("%d",&l); rep(i,0,20) for(int j=0;j<=n;j++) f[j][i]=inf; rep(i,1,n){ while(a[i]>a[j]+l) {f[j][0]=i-1;j++;} } rep(i,1,20) { c[i]=c[i-1]<<1; for(int j=1;j<=n;j++) if(f[j][i-1]!=inf){ //cout<<f[j][i-1]<<endl; f[j][i]=f[f[j][i-1]][i-1]; } } ans=0; scanf("%d",&q); rep(t,1,q) { int x,y,ans=0; scanf("%d%d",&x,&y); if(x>y) swap(x,y); dep(i,20,0) { if(f[x][i]<y) { x=f[x][i]; ans+=c[i]; } } printf("%d\n",ans+1); } } return 0; }