摘要
倍增优化 DP
小 A 和小 B 决定旅行，城市从 1 到 N 编号，编号较小的城市在编号较大的城市的西边，各个城市的海拔高度互不相同，记城市 i 的海拔高度为 ，城市 i 和城市 j 之间的距离 。
旅行过程中，小 A 和小 B 轮流开车，第一天小 A 开车，之后每天轮换一次。他们计划选择一个城市 S 作为起点，一直向东行驶，并且最多行驶 X 公里就结束旅行。小 B 总是沿着前进方向选择一个最近的城市作为目的地，而小 A 总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 X 公里，他们就会结束旅行。
在启程之前，小 A 想知道两个问题：
- 对于一个给定的 ，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
- 对任意给定的 和出发城市 ，小 A 开车行驶的路程总数以及小 B 行驶的路程总数。
.
题面长，复杂，懒得概括 emmm
好的这种题一看就是 DP。路程的范围太大显然不做为状态，于是 表示从城市 i 出发走 j 次，0/1 分别表示小 A/ 小 B 第一天开车，小 A 行驶的路程。同理 表示小 B 行驶的路程。这个 DP 的结果显然是单调的，因为走得多路程越多嘛。于是在查询的时侯可以二分查找。这样的复杂度是 ，显然无法接受。
经典套路， 表示从城市 i 出发走 次，0/1 分别表示小 A/ 小 B 第一天开车，小 A 行驶的路程。同理 表示小 B 行驶的路程。于是倍增优化后 DP 的复杂度就能降下来了。不过还需要维护一个 表示从城市 i 出发走 次，0/1 分别表示小 A/ 小 B 第一天开车，到达的城市。方程如下
由于 与 稍微有区别，因此要单独拿出来转移。 分别表示到达的最近的，第二近的城市编号，A,B 的转移同理
B 的就不写了，看代码
#include<cstdio>
#include<vector>
#include<algorithm>
#define fi first
#define se second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=1e5+5;
int n,x0;
int h[N];
struct data{int pre,nex,idx,h;};
data e[N];
int le;
bool cmp(data x,data y){return x.h<y.h;}
bool cmp2(data x,data y){return x.idx<y.idx;}
int n1[N],n2[N];
int d(int x,int y){return abs(h[x]-h[y]);}
int nex[N][18][2],A[N][18][2],B[N][18][2];
void prework(){
for(int i=1;i<=n;i++)nex[i][0][0]=n2[i], nex[i][0][1]=n1[i];
for(int i=1;i<=n;i++)nex[i][1][0]=n1[n2[i]],nex[i][1][1]=n2[n1[i]];
for(int j=2;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)<=n;i++){
nex[i][j][0]=nex[nex[i][j-1][0]][j-1][0];
nex[i][j][1]=nex[nex[i][j-1][1]][j-1][1];
}
}
for(int i=1;i<=n;i++)A[i][0][0]=d(i,n2[i]);
for(int i=1;i<=n;i++)A[i][1][0]=A[i][0][0], A[i][1][1]=A[n1[i]][0][0];
for(int j=2;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)<=n;i++){
A[i][j][0]=A[i][j-1][0]+A[nex[i][j-1][0]][j-1][0];
A[i][j][1]=A[i][j-1][1]+A[nex[i][j-1][1]][j-1][1];
}
}
for(int i=1;i<=n;i++)B[i][0][1]=d(i,n1[i]);
for(int i=1;i<=n;i++)B[i][1][0]=B[n2[i]][0][1], B[i][1][1]=B[i][0][1];
for(int j=2;(1<<j)<=n;j++){
for(int i=1;i+(1<<j)<=n;i++){
B[i][j][0]=B[i][j-1][0]+B[nex[i][j-1][0]][j-1][0];
B[i][j][1]=B[i][j-1][1]+B[nex[i][j-1][1]][j-1][1];
}
}
}
pii query(int x,int u){
// 从 u 出发行驶不超过 x 的 AB 路程
int a=0,b=0;
for(int j=17;j>=1;j--){
if(!u)break;// 相当于已经走到尽头
if(!nex[u][j][0])continue;
int dis=A[u][j][0]+B[u][j][0];
if(dis>x)continue;
a+=A[u][j][0],b+=B[u][j][0],x-=dis;
u=nex[u][j][0];
}
if(u)if(nex[u][0][0]&&A[u][0][0]<=x)a+=A[u][0][0];
return make_pair(a,b);
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&h[i]);
e[++le]=(data){0,0,i,h[i]};
}
sort(e+1,e+le+1,cmp);
for(int i=1;i<=n;i++){
e[i].pre=e[i-1].idx,e[i].nex=e[i+1].idx;
}
sort(e+1,e+le+1,cmp2);
for(int i=1;i<=n;i++){
int p=e[i].pre,pp=e[p].pre;
int q=e[i].nex,qq=e[q].nex;
int m=0x7fffffff,m2=0x7fffffff;
if(p&&d(p,i)<m)n1[i]=p,m=d(p,i);
if(q&&d(q,i)<m)n1[i]=q,m=d(p,i);
if(p&&p!=n1[i]&&d(p,i)<m2)n2[i]=p,m2=d(p,i);
if(pp&&pp!=n1[i]&&d(pp,i)<m2)n2[i]=pp,m2=d(pp,i);
if(q&&q!=n1[i]&&d(q,i)<m2)n2[i]=q,m2=d(q,i);
if(qq&&qq!=n1[i]&&d(qq,i)<m2)n2[i]=qq,m2=d(qq,i);
if(p)e[p].nex=q;
if(q)e[q].pre=p;
}
prework();
scanf("%lld",&x0);
pii a1=make_pair(1,0);
int ans1=0;
for(int i=1;i<=n;i++){
pii p=query(x0,i);
if(p.se==0&&p.fi==0)p.fi=1;// 无穷大处理
if(a1.fi*p.se>a1.se*p.fi)a1=p,ans1=i;
else if(a1.fi*p.se==a1.se*p.fi)ans1=h[ans1]>h[i]?ans1:i;
}
printf("%lld\n",ans1);
int m;
scanf("%lld",&m);
for(int i=1;i<=m;i++){
int x,s;
scanf("%lld%lld",&s,&x);
pii p=query(x,s);
printf("%lld %lld\n",p.fi,p.se);
}
return 0;
}
/*
* BUG#1:L71 没有用 idx
* BUG#2:L60L54 没有判断 nex 的存在性
* BUG#3:L81L82 pp 和 q 的顺序问题
*/
