题意:一条直线上有n个点x[i],x[i+1]-x[i]<=L,操作:每次可以从一个点跳到距离不超过其L的另一个点上.
Q次询问,问从a[j]点跳到b[j]点的最少操作次数? n<=1e5,x[i],L<=1e9 对每个询问:初始为i 令l=i+1,r=b[j] 二分最远能到达的点 最坏情况下O(QNlogN) TLE.. 其实每次操作就是把a[i]变到最右边一个满足,r[a[i]]-a[i]<=L. 每次查询就是求最少的r...r(r(a[i]))>=b[i] 设r[k][i] a[i]经过2^k次操作能达到最右边的位置 二分初始化r[0][i],r[k][i]=r[k-1][r[k-1][i]]查询时,找到最后一个i,r[i][u]<v 令u=r[i][u]继续逼近v.O((N+Q)logN)
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; const int N=2e5+20; const int M=5e2+20; const ll inf=2e15; ll n,x[N],L,Q; ll d[30][N]; void init() { for(ll i=1;i<=20;i++) { for(int j=1;j<=N;j++) { d[i][j]=d[i-1][d[i-1][j]]; } } } int main() { while(cin>>n) { for(int i=1;i<=n;i++) scanf("%I64d",&x[i]); cin>>L>>Q; for(int i=1;i<=n;i++) { int l=i+1,r=n; while(l<=r) { int mid=(l+r)>>1; if(x[mid]-x[i]<=L) l=mid+1; else r=mid-1; } d[0][i]=l-1; } init(); ll u,v; while(Q--) { scanf("%I64d%I64d",&u,&v); if(u>v) swap(u,v); ll ans=0; for(ll i=20;i>=0;i--) { if(d[i][u]<v) ans+=(1ll<<i),u=d[i][u]; } ans++; cout<<ans<<endl; } } return 0; }