题意
给定 \(n\) 座城市，第 \(i\) 座城市有一个海拔高度 \(h_i\)，且 \(h_i\) 两两不同。定义城市 \(i,j\) 的距离 \(dis(i,j)=|h_i-h_j|\)，即城市 \(i,j\) 海拔之差的绝对值。
小 A 和小 B 将从开车城市 \(s\) 出发，并且最多行驶 \(x\) 公里就结束旅行。他们会轮流驾驶，并且小 A 驾驶第一天。如果某一天是小 A 驾驶，那么他会在编号大于当前城市的城市中，选择离 \(s\) 最第二近的一个城市作为目的地；否则，小 B 会在编号大于当前城市的城市中，选择离 \(s\) 最近的城市作为目的地。特别地，如果有多个这样的城市，他们总会选择编号最小的。
如果某一天任何人都无法按照自己的原则选择出当天的目的地，或者到达目的地会使总路程数超过 \(x\) 公里，那么旅行结束。请求出：
-
对于一个给定的 \(x=x_0\)，从哪一个城市出发，小 A 开车行驶的路程总数与小 B 行驶的路程总数的比值最小（如果小 B 的行驶路程为 \(0\)，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小 A 开车行驶的路程总数与小B 行驶的路程总数的比值都最小，则输出海拔最高的那个城市。
-
对于给定的 \(m\) 个 \(s_i\) 和 \(x_i\)，小 A 开车行驶的路程总数和小 B 开车行驶的路程总数。
\(1 \leq n,m \leq 10^5,-10^9 \leq h_i \leq 10^9,1 \leq s_i \leq n,0 \leq x_i \leq 10^9\)
题解
首先，观察到每个人在城市固定的情况下的选择是固定的。
因为只能够选择编号大于等于当前的城市，所以可选择的是一个后缀。倒序处理，用 set 维护出每个人会选择的城市（set::lower_bound 查前驱，后继，前驱的前驱，后继的后继）。
其次，我们观察到，在不考虑 \(x\) 的影响下，每一天的决策与前一天的决策无关。这启发我们可以将几段决策拼到一起成为最终的决策。考虑倍增优化。设 \(\operatorname{id}_{i,k,0/1}\) 表示从城市 \(i\) 出发，小 A / 小 B 先开车，经过 \(2^k\) 天之后，到达的城市编号。同时，我们设 \(\operatorname{lena}_{i,k,0/1},\operatorname{lenb}_{i,k,0/1}\)，表示从城市 \(i\) 出发，小 A / 小 B 先开车，经过 \(2^k\) 天之后，小 A / 小 B 开车的路程总数。注意，上述的状态均不考虑 \(x\) 的影响。
我们可以轻松地预处理出 \(\operatorname{id}_{i,0,0/1}\)，对于 \(\operatorname{lena}\) 和 \(\operatorname{lenb}\) 同理。接下来，我们考虑转移。当 \(k>1\) 时，\(\operatorname{id}_{i,k,t}(t \in \{0,1\})\) 即 \(\operatorname{id}_{\operatorname{id}_{i,k-1,t},k-1,t}\)。而当 \(k=1\) 时，\(2^{k-1}=1\) 是一个奇数，所以前半部分是 \(t\) 先开车，而后半部分是 \(t \operatorname{xor} 1\) 先开车，需要注意。类似地，我们也可以得到 \(\operatorname{lena}\) 和 \(\operatorname{lenb}\) 的转移方程。有：
\(\operatorname{lenb}\) 同理。
对于第一问，枚举起点城市，然后倍增判断：如果从当前城市往前走 \(2^k\) 天路程总数不超过 \(x_0\)，那么就往前走。并分别记录下两人开车的路程数，比较比值即可。
对于第二问同理，记录下两人开车的路程数即可。
\(n\) 和 \(m\) 同阶，则时间复杂度为 \(O(n \log n)\)。
# include <bits/stdc++.h>
# define int long long
const int N=100010,INF=0x7fffffff;
struct Node{
int height,id;
bool operator < (const Node &rhs) const{
return height<rhs.height;
}
};
std::multiset <Node> S;
int h[N];
int n;
int nex[N][2];
int nexid[N][21][2],lena[N][21][2],lenb[N][21][2]; // nexid[] 即文中的 id[]
inline int read(void){
int res,f=1;
char c;
while((c=getchar())<'0'||c>'9')
if(c=='-')f=-1;
res=c-48;
while((c=getchar())>='0'&&c<='9')
res=res*10+c-48;
return res*f;
}
inline int myabs(int x){
return (x>0)?x:-x;
}
inline std::pair <int,int> calc(int st,int lim){
int la=0,lb=0,now=st;
for(int i=20;i>=0;--i){
if(nexid[now][i][0]&&la+lb+lena[now][i][0]+lenb[now][i][0]<=lim){ // 如果 nexid[now][i][0] == 0 则不能从当前点往前走 2^i 天
la+=lena[now][i][0],lb+=lenb[now][i][0];
now=nexid[now][i][0];
}
}
return std::make_pair(la,lb);
}
signed main(void){
n=read();
for(int i=1;i<=n;++i){
h[i]=read();
}
S.insert((Node){-INF,0}),S.insert((Node){-INF,0});
S.insert((Node){INF,0}),S.insert((Node){INF,0}); // 防止查不到而导致越界
for(int i=n;i;--i){
std::multiset <Node>::iterator l,r;
Node L,R,LL,RR;
l=r=S.lower_bound((Node){h[i],i});
--l,L=*l,R=*r;
--l,++r,LL=*l,RR=*r;
if(myabs(h[i]-L.height)<=myabs(h[i]-R.height)){
nex[i][1]=L.id;
if(myabs(h[i]-LL.height)<=myabs(h[i]-R.height)){
nex[i][0]=LL.id;
}else{
nex[i][0]=R.id;
}
}
else if(R.height!=INF){
nex[i][1]=R.id;
if(myabs(h[i]-L.height)<=myabs(h[i]-RR.height)){
nex[i][0]=L.id;
}else{
nex[i][0]=RR.id;
}
}
S.insert((Node){h[i],i});
}
for(int i=1;i<=n;++i){
nexid[i][0][0]=nex[i][0],nexid[i][0][1]=nex[i][1];
lena[i][0][0]=myabs(h[i]-h[nex[i][0]]),lenb[i][0][1]=myabs(h[i]-h[nex[i][1]]);
}
for(int k=1;k<=20;++k){
for(int i=1;i<=n;++i){
for(int s=0;s<=1;++s){
int mid=nexid[i][k-1][s];
if(k==1){
nexid[i][k][s]=nexid[mid][k-1][s^1];
lena[i][k][s]=lena[i][k-1][s]+lena[mid][k-1][s^1];
lenb[i][k][s]=lenb[i][k-1][s]+lenb[mid][k-1][s^1];
continue;
}
nexid[i][k][s]=nexid[mid][k-1][s];
lena[i][k][s]=lena[i][k-1][s]+lena[mid][k-1][s];
lenb[i][k][s]=lenb[i][k-1][s]+lenb[mid][k-1][s];
}
}
}
int X=read();
double minv=2e18;
int id;
for(int i=1;i<=n;++i){
std::pair <int,int> ans=calc(i,X);
int la=ans.first,lb=ans.second;
double nowv=(lb)?((double)la/(double)lb):(1e18);
if(minv>nowv||(minv==nowv&&h[id]<h[i])){
id=i,minv=nowv;
}
}
printf("%lld\n",id);
int m=read();
while(m--){
int si=read(),xi=read();
std::pair <int,int> ans=calc(si,xi);
printf("%lld %lld\n",ans.first,ans.second);
}
return 0;
}