题解 P1081 【开车旅行】
方法：倍增
题目坑点：
1.小A一次开到相邻第二近的城市，小B一次开到相邻第一近的城市
2.在第一个问题中，如果从多个城市出发时比值相同，取海拔最大的城市
3.只能向东行驶，即不能从后输入的城市开到先输入的城市
预处理
预处理1：
通过倒序求出小A和小B从每个城市i出发，沿前进方向行驶到的下一个城市，分别记为ga[i],gb[i]，注意ga[i]是相邻的第二个城市
方法：STL-set/双向链表/手写平衡树,我选择了后者
预处理2：目的地
设
显然，
当i=1时，因为2^0=1是奇数，所以两人从j出发2^1天等于小A开一天，小B开一天
即
当i>1时，因为2^i是偶数，所以前后半程都是k先开车
即
PS：注意ga，gb，f超出边界的情况，在这里我把数组开大了一些
预处理3（dp）：行驶路程长度
设
设
显然，
dis(i,j)表示i号城市和j号城市的海拔差的绝对值，即i城与j城的距离
当i=1时，da[0][j][k]为第一天小a行驶的路程，da[0][f[0][j][k]][1-k]为第二天小a行驶的路程
同理
当i>1时，
∴
同理
回答询问
对于问题2
初始化当前城市p=S，小A、小B分别累计行驶了la，lb的路程
倒序循环i=logn~0
对于每个i，若两人已行驶路程+从p行驶2^i的路程仍<=X,
即
则加上这一段路程，并更新p的位置
即
循环结束后la，lb为所求
对于问题1
只要枚举出发城市，并执行问题2的解法，最后再找出la：lb比值最小的城市输出即可
//码风略丑
#include <set>
#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int n,x0,m,s,x;
double ans;
long long h[100005],ga[100005],gb[100005];
long long f[18][100005][2];
long long da[18][100005][2],db[18][100005][2];
const int INF=0x7fffffff;
long long Abs(long long sum){
if(sum<0)return -sum;
return sum;
}
namespace tree{
struct treap{
int l,r,val,dat,note;
}a[100005];
int tot,root;
int New(int val){
a[++tot].val=val;
a[tot].dat=rand();
a[tot].note=n+3-tot;
return tot;
}
void build(){
New(-INF);New(INF);
root=1;a[root].r=2;
}
void zig(int &p){
int q=a[p].l;
a[p].l=a[q].r;a[q].r=p;p=q;
}
void zag(int &p){
int q=a[p].r;
a[p].r=a[q].l;a[q].l=p;p=q;
}
void ins(int &p,int val){
if(p==0){
p=New(val);
return ;
}
if(a[p].val<val){
ins(a[p].r,val);
if(a[a[p].r].dat>a[p].dat)zag(p);
}
else{
ins(a[p].l,val);
if(a[a[p].l].dat>a[p].dat)zig(p);
}
}
int pre(int val){
int ans=1,p=root;
while(p!=0){
if(a[p].val==val){
if(a[p].l){
p=a[p].l;
while(a[p].r)p=a[p].r;
ans=p;
}
break;
}
if(a[p].val<val&&a[p].val>a[ans].val)ans=p;
if(a[p].val>val)p=a[p].l;
else p=a[p].r;
}
return a[ans].note;
}
int suc(int val){
int ans=2,p=root;
while(p!=0){
if(a[p].val==val){
if(a[p].r){
p=a[p].r;
while(a[p].l)p=a[p].l;
ans=p;
}
break;
}
if(a[p].val>val&&a[p].val<a[ans].val)ans=p;
if(a[p].val>val)p=a[p].l;
else p=a[p].r;
}
return a[ans].note;
}
}
int cal_gab(){//计算ga和gb
using namespace tree;
build();
int s1,s2,s3,s4;
h[n+1]=INF;h[n+2]=-INF;
for(int i=n;i>=1;i--){
ins(root,h[i]);
s1=pre(h[i]);s2=pre(h[s1]);
s3=suc(h[i]);s4=suc(h[s3]);
if(Abs(h[i]-h[s1])<=Abs(h[i]-h[s3])){
gb[i]=s1;
if(Abs(h[i]-h[s2])<=Abs(h[i]-h[s3]))ga[i]=s2;
else ga[i]=s3;
}
else{
gb[i]=s3;
if(Abs(h[i]-h[s1])<=Abs(h[i]-h[s4]))ga[i]=s1;
else ga[i]=s4;
}
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&h[i]);
cal_gab();
for(int i=1;i<=n;i++)
f[0][i][0]=ga[i],f[0][i][1]=gb[i];
for(int i=1;i<=n;i++){
f[1][i][0]=f[0][f[0][i][0]][1];
f[1][i][1]=f[0][f[0][i][1]][0];
}
for(int i=2;i<=17;i++){
for(int j=1;j<=n;j++){
for(int k=0;k<=1;k++){
f[i][j][k]=f[i-1][f[i-1][j][k]][k];
}
}
}//计算f
for(int j=1;j<=n;j++){
da[0][j][0]=Abs(h[j]-h[ga[j]]);
db[0][j][1]=Abs(h[j]-h[gb[j]]);
}
for(int j=1;j<=n;j++){
for(int k=0;k<=1;k++){
da[1][j][k]=da[0][j][k]+da[0][f[0][j][k]][1-k];
db[1][j][k]=db[0][j][k]+db[0][f[0][j][k]][1-k];
}
}
for(int i=2;i<=17;i++){
for(int j=1;j<=n;j++){
for(int k=0;k<=1;k++){
da[i][j][k]=da[i-1][j][k]+da[i-1][f[i-1][j][k]][k];
db[i][j][k]=db[i-1][j][k]+db[i-1][f[i-1][j][k]][k];
}
}
}//计算da，db
ans=INF;int wans=0;h[0]=-INF;ans=INF;
scanf("%d%d",&x0,&m);
for(int T=1;T<=n;T++){
double la=0,lb=0;
int p=T;
for(int i=17;i>=0;i--){
if(la+lb+da[i][p][0]+db[i][p][0]<=x0){
la+=da[i][p][0];
lb+=db[i][p][0];
p=f[i][p][0];
}
}
if(lb==0){
if(ans==INF&&h[T]>h[wans])wans=T;
}
else if((ans>(la*1.0/lb*1.0))||((ans==(la*1.0/lb*1.0))&&h[T]>h[wans]))ans=(la*1.0/lb*1.0),wans=T;
}
printf("%d\n",wans);
for(int T=1;T<=m;T++){
scanf("%d%d",&s,&x);
double la=0,lb=0;
int p=s;
for(int i=17;i>=0;i--){
if(la+lb+da[i][p][0]+db[i][p][0]<=x){
la+=da[i][p][0];
lb+=db[i][p][0];
p=f[i][p][0];
}
}
printf("%.0lf %.0lf\n",la,lb);
}
}