AT_arc060_c 题解

AlicX · 2023-10-19 11:22:10 · 题解

Solution

很经典的套路题。

显然地，对于 i 号旅店来说，每次走 j 步可以到达的旅店是确定的，所以考虑 O(n^2) 预处理出 f_{i,j} 表示从 i 号旅店开始走走 j 步可以到达的旅店，然后参考倍增思想，有一个经典的优化：f_{i,j} 表示从 i 号旅店走 2^j 步可以到达的旅店，则可以用二分找出 f_{i,0}，然后依次递推：f_{i,j}=f_{f_{i,j-1},j-1}，询问的时候从 a 开始跳向 b 点即可。时间复杂度为 O(n \log n)。

const int N=1e5+10,M=20,INF=1e9+7;  
int L;  
int n,m;
int a[N]; 
int f[N][M]; 
signed main(){ 
    scanf("%d",&n); 
    for(int i=1;i<=n;i++) scanf("%d",&a[i]); a[n+1]=2*INF; 
    scanf("%d",&L); for(int i=1;i<=n;i++) f[i][0]=upper_bound(a+1,a+n+2,a[i]+L)-a-1; 
    for(int j=1;j<M;j++) for(int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; 
    scanf("%d",&m); 
    while(m--){ int ans1=0,ans2=INF; 
        int s,t; scanf("%d%d",&s,&t); if(s>t) swap(s,t); 
        for(int j=M-1;j>=0;j--) if(f[s][j]<t) s=f[s][j],ans2=min(ans2,ans1+(1<<(j+1))),ans1+=(1<<j);  
        printf("%d\n",min(ans2,ans1+1)); 
    } return 0; 
} /* */