【AtCoder Regular Contest 060 E】Tak and Hotels | Mrsrz's blog

倍增。

题目大意：

给定 $n$ 个旅店在数轴上的位置（从左到右），和一天最多行驶的距离 $L$。

多组询问，每次给出 $a,b$，问从 $a$ 至少几天才能到 $b$。每天的终点必须是一个旅店。

题解：

容易想到倍增。

用 $f_{i,j}$ 表示走 $2^i$ 天，从 $j$ 出发能到达的最右边的点。

由于 $L$ 是固定的，所以每次从最右边的点继续走一定是最优的。

所以预处理的时候，$f_{i,j}=f_{i-1,f_{i-1,j}}$ 即可。

往左走同理。

求答案就类似树上求 LCA 的操作，从大到小枚举 $i$，如果 $2^i$ 天还没到就跳过去。最后还得再补 $1$。

时间复杂度 $O((n+q)\log n)$。

Code：

#include<cstdio>
const int N=1e5+9;
int L[17][N],R[17][N],n,t,q,X[N],ans;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i)scanf("%d",X+i);
    scanf("%d",&t);
    for(int i=1,it=1;i<=n;++i){
        while(it<n&&X[it+1]-X[i]<=t)++it;
        R[0][i]=it;
    }
    for(int i=n,it=n;i;--i){
        while(it>1&&X[i]-X[it-1]<=t)--it;
        L[0][i]=it;
    }
    for(int i=1;i<17;++i)
    for(int j=1;j<=n;++j)
    R[i][j]=R[i-1][R[i-1][j]],L[i][j]=L[i-1][L[i-1][j]];
    for(scanf("%d",&q);q--;printf("%d\n",ans)){
        int x,y;ans=1;
        scanf("%d%d",&x,&y);
        if(x<=y){
            for(int i=16;~i;--i)
            if(R[i][x]<y)ans+=1<<i,x=R[i][x];
        }else{
            for(int i=16;~i;--i)
            if(L[i][x]>y)ans+=1<<i,x=L[i][x];
        }
    }
    return 0;
}