小 \(\text{A}\) 和小 \(\text{B}\) 决定利用假期外出旅行，他们将想去的城市从 $1 $ 到 \(n\) 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 \(i\) 的海拔高度为\(h_i\)，城市 \(i\) 和城市 \(j\) 之间的距离 \(d_{i,j}\) 恰好是这两个城市海拔高度之差的绝对值，即 \(d_{i,j}=|h_i-h_j|\)。
旅行过程中，小 \(\text{A}\) 和小 \(\text{B}\) 轮流开车，第一天小 \(\text{A}\) 开车，之后每天轮换一次。他们计划选择一个城市 \(s\) 作为起点，一直向东行驶，并且最多行驶 \(x\) 公里就结束旅行。
小 \(\text{A}\) 和小 \(\text{B}\) 的驾驶风格不同，小 \(\text{B}\) 总是沿着前进方向选择一个最近的城市作为目的地，而小 \(\text{A}\) 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 \(x\) 公里，他们就会结束旅行。
在启程之前，小 \(\text{A}\) 想知道两个问题：
对于一个给定的 \(x=x_0\)，从哪一个城市出发，小 \(\text{A}\) 开车行驶的路程总数与小 \(\text{B}\) 行驶的路程总数的比值最小（如果小 \(\text{B}\) 的行驶路程为 \(0\)，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 \(\text{A}\) 开车行驶的路程总数与小 \(\text{B}\) 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
对任意给定的 \(x=x_i\) 和出发城市 \(s_i\)，小 \(\text{A}\) 开车行驶的路程总数以及小 \(\text B\) 行驶
的路程总数。
假设这个并非是必须向东行驶。
我们可以对 \(h\) 数组进行排序。
则排好序的第 \(x\) 个城市，第 \(1\) 近的城市和第 \(2\) 进的城市，一定在 \(x-2,x-1,x+1,x+2\) 这些城市当中。
那么向东行驶怎么处理呢？
我们可以用这样一个思想：
首先，想让第 \(x\) 个城市没有向东行的限制，可以直接把 \(1 \sim x-1\) 这 \(x-1\) 个城市删掉。
这样就可以解除向东行的限制。
我们可以试着用一个链表，来模拟这个东西。
priority_queue<pair<int,pair<int,int> > >q;
read(n);
for(int i=1;i<=n;i++){
read(m[i].h);
m[i].id=i;
}sort(m+1,m+n+1,cmp);
for(int i=1;i<=n;i++){
id[m[i].id]=i;
pre[i]=i-1;lat[i]=i+1;
}
for(int i=1;i<=n;i++){
while(q.size())q.pop();
int x=id[i];
int p1=pre[x],p2=pre[pre[x]],l1=lat[x],l2=lat[lat[x]];
bool pb1=true,pb2=true,lb1=true,lb2=true;
if(p1<=0)pb1=false;
else if(p2<=0)pb2=false;
if(l1>n)lb1=false;
else if(l2>n)lb2=false;
if(pb1){
q.push(make_pair(-abs(m[x].h-m[p1].h),make_pair(-m[p1].h,p1)));
if(pb2)q.push(make_pair(-abs(m[x].h-m[p2].h),make_pair(-m[p2].h,p2)));
}
if(lb1){
q.push(make_pair(-abs(m[x].h-m[l1].h),make_pair(-m[l1].h,l1)));
if(lb2)q.push(make_pair(-abs(m[x].h-m[l2].h),make_pair(-m[l2].h,l2)));
}
if(q.size())fi[i]=m[q.top().second.second].id;
if(q.size())q.pop();
if(q.size())se[i]=m[q.top().second.second].id;
lat[p1]=lat[x];pre[l1]=pre[x];
}
我这里是用一个堆，\(push\) 了 \(\leq 4\) 个可能的数，然后搞。
之后就直接倍增，这里就不详细讲了
#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(T &FF){
T RR=1;FF=0;char CH=getchar();
for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1;
for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48);
FF*=RR;
}
const int MAXN=1e5+10;
struct node{
int h,id;
}m[MAXN];
int n,id[MAXN],pre[MAXN],lat[MAXN],fi[MAXN],se[MAXN],f[MAXN][25],a[MAXN][25],b[MAXN][25],A,B;
double Min=10000000000;
priority_queue<pair<int,pair<int,int> > >q;
bool cmp(node a,node b){
return a.h<b.h;
}
void work(int x,int x1){
A=0;B=0;
for(int j=19;j>=0;j--)
if(f[x1][j]&&(A+B+a[x1][j]+b[x1][j])<=x){
A+=a[x1][j];
B+=b[x1][j];
x1=f[x1][j];
}
if(se[x1]&&A+B+a[x1][0]<=x)A+=a[x1][0];
}
int main(){
read(n);
for(int i=1;i<=n;i++){
read(m[i].h);
m[i].id=i;
}sort(m+1,m+n+1,cmp);
for(int i=1;i<=n;i++){
id[m[i].id]=i;
pre[i]=i-1;lat[i]=i+1;
}
for(int i=1;i<=n;i++){
while(q.size())q.pop();
int x=id[i];
int p1=pre[x],p2=pre[pre[x]],l1=lat[x],l2=lat[lat[x]];
bool pb1=true,pb2=true,lb1=true,lb2=true;
if(p1<=0)pb1=false;
else if(p2<=0)pb2=false;
if(l1>n)lb1=false;
else if(l2>n)lb2=false;
if(pb1){
q.push(make_pair(-abs(m[x].h-m[p1].h),make_pair(-m[p1].h,p1)));
if(pb2)q.push(make_pair(-abs(m[x].h-m[p2].h),make_pair(-m[p2].h,p2)));
}
if(lb1){
q.push(make_pair(-abs(m[x].h-m[l1].h),make_pair(-m[l1].h,l1)));
if(lb2)q.push(make_pair(-abs(m[x].h-m[l2].h),make_pair(-m[l2].h,l2)));
}
if(q.size())fi[i]=m[q.top().second.second].id;
if(q.size())q.pop();
if(q.size())se[i]=m[q.top().second.second].id;
lat[p1]=lat[x];pre[l1]=pre[x];
}
for(int i=1;i<=n;i++){
f[i][0]=fi[se[i]];
a[i][0]=abs(m[id[i]].h-m[id[se[i]]].h);
b[i][0]=abs(m[id[fi[se[i]]]].h-m[id[se[i]]].h);
}
for(int j=1;j<=20;j++)
for(int i=1;i<=n;i++){
f[i][j]=f[f[i][j-1]][j-1];
a[i][j]=a[i][j-1]+a[f[i][j-1]][j-1];
b[i][j]=b[i][j-1]+b[f[i][j-1]][j-1];
}
int x,ans;read(x);
for(int i=1;i<=n;i++){
work(x,i);
if(B&&1.0*A/B<Min){
Min=1.0*A/B;
ans=i;
}
}cout<<ans<<endl;
int T;for(read(T);T--;){
int j,x;read(j);read(x);
work(x,j);
printf("%d %d\n",A,B);
}
return 0;
}