预备知识——关于set的用法

定义：set<int>s;</int>

本题需要用到的几个函数:

s.insert(x);//插入x
s.lower_bound(x);//查找**大于等于**x的最小元素，返回迭代器
s.upper_bound(x);//查找**大于**x的最小元素，返回迭代器

在本题运用set能够使初始化的复杂度降到O(nlogn)

s.insert(h[i]);
t[1].h=*--s.lower_bound(h[i]);
t[3].h=*--s.lower_bound(t[1].h); 
t[2].h=*s.upper_bound(h[i]); 
t[4].h=*s.upper_bound(t[2].h);
for(int j=1;j<=4;j++)t[j]._abs=abs(t[j].h-h[i]);
sort(t+1,t+5,cmp);
a[i]=t[2]._abs;f
a[i]=mp[t[2].h];
b[i]=t[1]._abs;fb[i]=mp[t[1].h];
if(fa[i])sa[i][0]=a[i],f[i][0]=fa[i];
if(fb[fa[i]])sa[i][1]=a[i],sb[i][1]=b[fa[i]],f[i][1]=fb[fa[i]];

回归正题，由于本题木有修改操作，并且到每个点的下一个点的位置确定，很容易想到倍增来优化，同时由于本题的需要，除f[i][j]外，在定义两个数组sa[i][j]和sb[i][j]],分别表示第i个点走2^j天A所走的路程和B所走的路程。

废话少说，直接上代码：

#include<bits/stdc++.h>
#define INF 50000000000LL
#define A 100005
using namespace std;
struct note{
    long long h,_abs;
}t[5];
set<long long>s;
map<long long,long long>mp;
long long n,h[A],a[A],b[A],fa[A],fb[A],sa[A][25],sb[A][25],f[A][25];
bool cmp(note aa,note bb){
    return (aa._abs==bb._abs?aa.h<bb.h:aa._abs<bb._abs);
}
void st(){
    for(long long i=n;i>=1;i--){
        s.insert(h[i]);
        t[1].h=*--s.lower_bound(h[i]);
        t[3].h=*--s.lower_bound(t[1].h); 
        t[2].h=*s.upper_bound(h[i]); 
        t[4].h=*s.upper_bound(t[2].h);
        for(long long j=1;j<=4;j++)t[j]._abs=abs(t[j].h-h[i]);
        sort(t+1,t+5,cmp);
        a[i]=t[2]._abs;fa[i]=mp[t[2].h];
        b[i]=t[1]._abs;fb[i]=mp[t[1].h];
        if(fa[i])sa[i][0]=a[i],f[i][0]=fa[i];
        if(fb[fa[i]])sa[i][1]=a[i],sb[i][1]=b[fa[i]],f[i][1]=fb[fa[i]];
        for(long long j=2;j<=16;j++)
            if(f[f[i][j-1]][j-1]){
                sa[i][j]=sa[i][j-1]+sa[f[i][j-1]][j-1];
                sb[i][j]=sb[i][j-1]+sb[f[i][j-1]][j-1];
                f[i][j]=f[f[i][j-1]][j-1];
            }
            else break;
    }
}
double ask1(long long x,long long p){
    long long s1=0,s2=0;
    for(long long i=16;i>=0;i--){
        if(f[x][i]&&s1+s2+sa[x][i]+sb[x][i]<=p){
            s1+=sa[x][i];
            s2+=sb[x][i];
            x=f[x][i];
        }
    }
    return (s2==0?INF:(double)s1/(double)s2);
}
void ask2(long long x,long long p){
    long long s1=0,s2=0;
    for(long long i=16;i>=0;i--){
        if(f[x][i]&&s1+s2+sa[x][i]+sb[x][i]<=p){
            s1+=sa[x][i];
            s2+=sb[x][i];
            x=f[x][i];
        }
    }
    if(fa[x]&&s1+s2+sa[x][0]<=p)s1+=sa[x][0];
    printf("%lld %lld\n",s1,s2);
}
void solve(){ 
    double minn=INF;
    long long bj,x0;
    scanf("%lld",&x0);
    for(long long i=1;i<=n;i++){
        double op=ask1(i,x0);
        if(op<minn)minn=op,bj=i;
    }
    printf("%lld\n",bj);
    long long m,s0;
    scanf("%lld",&m);
    while(m--){
        scanf("%lld%lld",&s0,&x0);
        ask2(s0,x0);
    }
}
int main(){
    s.insert(INF);s.insert(INF-1);s.insert(-INF);s.insert(-INF+1);
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++)scanf("%lld",&h[i]),mp[h[i]]=i;
    st();
    solve();
    return 0;
}

结束语：此题不要想得太难，就是一道LCA的加强版，然后在初始化时加上set或链表（本蒟蒻不懂大佬写的链表，所以只有写set了）