讲解 P1081 [NOIP2012 提高组] 开车旅行。

使用 set 快速求出最近点与次近点，然后使用倍增优化 dp。

思路：

首先令 \(nxt1_i\) 表示右侧最近的城市距离（\(id1_i\) 为编号），令 \(nxt2_i\) 表示右侧第二近的城市编号（\(id2_i\) 为编号）；可以使用 <code>set 找出离这个城市最近的 \(4\) 个城市（前面两个，后面两个）。

定义：

• \(f_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后到达的位置。

• \(dp1_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后 A 走过的距离。

• \(dp2_{i,j}\) 表示从 \(i\) 点出发走 \(2^j\) 轮最后 B 走过的距离。

初始化：

\[f_{i,0} = id1_{id2_i}

\]

\[dp1_{i,0} = nxt2_{i}

\]

\[dp2_{i,0} = nxt1_{id2_i}

\]

状态转移方程为：

\[f_{i,j} = f_{f_{i,j-1},j-1}

\]

\[dp1_{i,j} = dp1_{i,j-1} + dp1_{f_{i,j-1},j-1}

\]

\[dp2_{i,j} = dp2_{i,j-1} + dp2_{f_{i,j-1},j-1}

\]

此时对于询问 \(1\) 和询问 \(2\)：

• 本质上是求出从每个城市出发后 \(A\) 走的距离与 \(B\) 走的距离。

• 那么考虑从高位到低位贪心，即设当前跳到了 \(s\) 点，若 \(dp1_{s,i} + dp2_{s,i} \le x\)，可以从 \(s\) 跳到 \(f_{s,i}\)，需要令 \(x \gets x - (dp1_{s,i} + dp2_{s,i})\)，然后继续遍历 \(i-1\) 位。

• 因为是 A 先开车，所以 A 可能会在最后一轮结束后还能再开上一次，需要特判。

时间复杂度为 \(O((N+Q) \log N)\)。

完整代码：

#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=1e5+10,M=18,INF=1e18;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

struct Node{

ll a,b;

ll id;

bool operator<(const Node&rhs)const{

if(a!=rhs.a)

return a<rhs.a;

return b<rhs.b;

}

};

ll n,m,s,x,x0,s0,cnt,dis1,dis2,disa,disb;

ll a[N],nxt1[N],nxt2[N],id1[N],id2[N];

ll f[N][M],dp1[N][M],dp2[N][M];

Node h[N];

vector<Node> V;

multiset<Node> S;

void solve(ll s,ll x){

dis1=dis2=0;

for(int i=M-1;i>=0;i--){

if(dp1[s][i]+dp2[s][i]<=x&&f[s][i]){

dis1+=dp1[s][i],dis2+=dp2[s][i];

x-=dp1[s][i]+dp2[s][i];

s=f[s][i];

}

}

if(nxt2[s]<=x)

dis1+=nxt2[s];

}

bool End;

int main(){

n=read();

for(int i=1;i<=n;i++){

a[i]=read();

h[i]={a[i],a[i],i};

}

S.insert({INF,INF,0});

S.insert({INF-1,INF-1,0});

S.insert({-INF,-INF,0});

S.insert({-INF+1,-INF+1,0});

for(int i=n;i>=1;i--){

V.clear();

V.push_back(*--S.lower_bound(h[i]));

V.push_back(*--S.lower_bound(V[0]));

V.push_back(*S.upper_bound(h[i]));

V.push_back(*S.upper_bound(V[2]));

for(auto &v:V)

v.a=abs(h[i].a-v.a);

sort(V.begin(),V.end());

nxt1[i]=V[0].a,nxt2[i]=V[1].a;

id1[i]=V[0].id,id2[i]=V[1].id;

cerr<<id1[i]<<' '<<id2[i]<<'\n';

S.insert(h[i]);

}

for(int i=1;i<=n;i++){

f[i][0]=id1[id2[i]];

dp1[i][0]=nxt2[i];

dp2[i][0]=nxt1[id2[i]];

}

for(int j=1;j<M;j++){

for(int i=n;i>=1;i--){

f[i][j]=f[f[i][j-1]][j-1];

dp1[i][j]=dp1[i][j-1]+dp1[f[i][j-1]][j-1];

dp2[i][j]=dp2[i][j-1]+dp2[f[i][j-1]][j-1];

}

}

x0=read();

for(int i=1;i<=n;i++){

solve(i,x0);

if(dis2&&(!s0||disa*dis2>disb*dis1)){

s0=i;

disa=dis1,disb=dis2;

}

}

write(s0);

putchar('\n');

m=read();

while(m--){

s=read(),x=read();

solve(s,x);

write(dis1);

putchar(' ');

write(dis2);

putchar('\n');

}

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}