蛤的旅行

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define debug prllf("*");
//#define mo 1e9+7
const ll N=1e5+5;
ll n,m,x[N],st[N][20];
int main(){
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&x[i]);
    ll l=1,r=n-m+1;
    for(ll i=1;i<=n;i++){
        while(abs(x[i]-x[l])>abs(x[r+1]-x[i])) l++,r++;
        if(abs(x[i]-x[l])>=abs(x[r]-x[i])) st[i][0]=l;//第m远 
        else st[i][0]=r;
    } 
    for(ll j=1;j<=18;j++)
        for(ll i=1;i<=n;i++)
            st[i][j]=st[st[i][j-1]][j-1];
    ll q,s,c;scanf("%lld",&q);
    for(ll i=1;i<=q;i++){
        scanf("%lld%lld",&s,&c);
        for(ll i=0;i<=18;i++)
            if(c&(1<<i)) s=st[s][i];
        printf("%lld\n",s);
    }
    return 0;
}

蛤的旅行

原文：https://www.cnblogs.com/zdsrs060330/p/12346346.html