题意：
给n个点的海拔h[i]（不同点海拔不同） 两点的距离为abs(h[i]-h[j]) 有a、b两人轮流开车（只能往下标大的地方开） a每次会开到里当前点第二近的点 b每次会开到离当前点最近的点（距离相同h小的近） 给定x 如果a或b继续开距离和会大于x就不继续开。
求两个问题
1、给定x=x0求从哪点开始开能使a开的距离：b开的距离最小 不值相同取海拔高的
2、给出m个询问 每个询问给定x1、y1 求从x1开始走且x=y1 a能走的距离和b能走的距离
题解：
不难发现（其实我一开始没发现 看了题解才知道TAT）从固定某点i走到的后若干个点和x没关系
我们可以预处理出从i点走j个点 a、b走的距离 由于数据略大 可以用倍增做 move[i][j] 表示i开始走2^j步 a、b走的距离
由于n比较大 不能n^2直接算离某点最近和第二进的点是谁
可以先把所有的h[i]拿来排序 建立双向链表 显然i点的最近点一定是双向链表中i的前驱或后继 而次近点则还可能是前驱的前驱或后继的后继 每次求完将该点从双向链表中删除 这样就能o(n) 求出最近和次近点了
然后我们就可以倍增轻松求出i开始走 且a、b走的距离<=x a、b分别走了多远了（第二个问题解决）
对于第一个问题 也很简单 直接枚从哪个点开始走算ans就完了
代码：
#include <cstdio>
#include <algorithm>
typedef long long ll;
using std::sort;
const ll N=;
struct info{
ll t,ma,mb,bo;
info(const ll a=,const ll b=,const ll c=,const ll d=):
t(a),ma(b),mb(c),bo(d){}
}move[N][][],save;
struct inli{
ll t,pr,ne;
inli(const ll a=,const ll b=,const ll c=):
t(a),pr(b),ne(c){}
}line[N];
struct inim{
ll t,s;
inim(const ll a=,const ll b=):
t(a),s(b){}
}im[N];
inline bool cmp(inim x,inim y){ return x.t<y.t; }
ll h[N],sp[N],n,m,x0,ans;
void makeline(){
for (ll i=;i<=n;i++){
line[i].t=im[i].s;
if (i>) line[i].pr=i-;
if (i<n) line[i].ne=i+;
}
}
void makeres(ll &res1,ll &res2,ll t,ll a1){
if (!a1) return;
if (res1== || abs(h[t]-h[a1])<abs(h[t]-h[res1]) ||
(abs(h[t]-h[a1])==abs(h[t]-h[res1]) && h[a1]<h[res1])) res2=res1,res1=a1;
else if (res2== || abs(h[t]-h[a1])<abs(h[t]-h[res2]) ||
(abs(h[t]-h[a1])==abs(h[t]-h[res2]) && h[a1]<h[res2])) res2=a1;
}
inim getmove(ll t,ll a1,ll a2,ll a3,ll a4){
ll res1=,res2=;
if (t==)
t=;
makeres(res1,res2,t,line[a1].t);
makeres(res1,res2,t,line[a2].t);
makeres(res1,res2,t,line[a3].t);
makeres(res1,res2,t,line[a4].t);
if (!res1) return inim(res2,res1);
return inim(res1,res2);
}
void makemove0(){
for (ll i=;i<n;i++){
if (i==)
i=;
inim x=getmove(i,line[sp[i]].pr,line[sp[i]].pr ? line[line[sp[i]].pr].pr : ,
line[sp[i]].ne,line[sp[i]].ne ? line[line[sp[i]].ne].ne : );
move[i][][].t=x.t;
move[i][][].ma=abs(h[i]-h[x.t]);
move[i][][].bo=;
if (x.s){
move[i][][].t=x.s;
move[i][][].mb=abs(h[i]-h[x.s]);
move[i][][].bo=;
}
line[line[sp[i]].pr].ne=line[sp[i]].ne;
line[line[sp[i]].ne].pr=line[sp[i]].pr;
}
}
void makemove(){
makemove0();
for (ll i=n;i;i--)
for (ll k=;k<=;k++){
if (i==)
i=;
for (ll j=;move[move[i][j-][k].t][j-][move[i][j-][k].bo].t;j++){
info x=move[move[i][j-][k].t][j-][move[i][j-][k].bo];
move[i][j][k].t=x.t;
move[i][j][k].bo=x.bo;
move[i][j][k].ma=move[i][j-][k].ma+x.ma;
move[i][j][k].mb=move[i][j-][k].mb+x.mb;
}
}
}
info getans(ll x,ll y){
info res=info(x,,,);
for (;y>=move[res.t][][res.bo].ma+move[res.t][][res.bo].mb && move[res.t][][res.bo].t;){
ll i=,st=res.t,sb=res.bo;
while (y>=move[st][i][sb].ma+move[st][i][sb].mb && move[st][i][sb].t) ++i;
--i;
y-=move[st][i][sb].ma+move[st][i][sb].mb;
res.t=move[st][i][sb].t;
res.bo=move[st][i][sb].bo;
res.ma+=move[st][i][sb].ma;
res.mb+=move[st][i][sb].mb;
}
return res;
}
bool check(info x,ll y){
if (!ans) return ;
if (!x.ma){
if (save.ma) return ;
else return (h[y]>h[ans]);
}
if (!save.mb) return ;
if (save.ma*x.mb<save.mb*x.ma || (save.ma*x.mb==save.mb*x.ma && h[y]>h[ans])) return ;
else return ;
}
int main(){
freopen("drive.in","r",stdin);
freopen("drive.out","w",stdout);
scanf("%I64d",&n);
for (ll i=;i<=n;i++){
scanf("%I64d",&h[i]);
im[i]=inim(h[i],i);
}
sort(im+,im+n+,cmp);
for (ll i=;i<=n;i++) sp[im[i].s]=i;
makeline();
makemove();
scanf("%I64d",&x0);
for (ll i=;i<=n;i++){
info x=getans(i,x0);
if (check(x,i)) save=x,ans=i;
}
printf("%I64d\n",ans);
scanf("%I64d",&m);
ll x,y;
for (ll i=;i<=m;i++){
if (i==)
i=;
scanf("%I64d%I64d",&x,&y);
info xx=getans(x,y);
printf("%I64d %I64d\n",xx.mb,xx.ma);
}
fclose(stdin);
fclose(stdout);
}