题意分析
首先发现，$n,q\leq2\times 10^5$，$\mathcal O(q)$ 肯定是不能省略的。
每一个询问其实都差不多，因此考虑如何高效的求出总旅行距离。
性质
记 $(p,q)$ 表示节点 $p\sim q$ 的距离，即 $\vert x_p-x_q\vert$。
令当前起始坐标为 $s$。首先可以通过一次二分求出离 $s$ 最近的节点 $p$。
显然，走过的节点一定是在一段连续区间内，记该区间为 $[l,r]$。（$l,r$ 表示节点编号）
如果打一个暴力，就会发现转向次数不会很多。
不妨令 Bitaro 上一次在 $r$ 处向左转向走到 $l$，在 $l$ 处向右转向，走到 $r+1$ 后继续向右走。
则有：
\[(r,r+1)\geq(l,r)\]考虑反证。
假设 $(r,r+1)<(l,r)$ 成立。
则：
\[(r,r+1)<(r-1,r)+(r-2,r-1)+(r-3,r-2)+\cdots(l,l+1)\]考虑到在 $r$ 处是向左走走到 $r-1$，因此 $(r-1,r)<(r,r+1)$，与上式矛盾。
故假设不成立。
这样的话，每次转向之前走的路程就是指数级增长的，则转向次数为 $\mathcal O(\log V)$，其中 $V$ 为坐标值域。
那就可以考虑如何快速地跳到转向的位置，可以考虑二分。
以向左走，扩展左边界寻找向右转向的位置 $l’$ 为例。
记当前区间为 $[l,r]$。
二分一个节点 $p$，使得 $x_p\geq x_l-(r+1,l)$ 且 $p$ 最小。
-
若 $p<l$，就代表 $p$ 是一个可行的 $l’$ 且是最小的 $l’$，那么就找到了转向点。
-
否则若 $p\geq l$，就代表不可转向，只能继续走。
但是实际上这一部分用什么都可以，ST 表倍增也可以，数据结构维护也可以。
AC 代码
时间复杂度：$\mathcal O(q\log V\log n)$。
其中，$\mathcal O(\log n)$ 是二分带来的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
//#define DEBUG
typedef long long ll;
constexpr const int N=2e5,Q=2e5;
constexpr const ll Ans=N*1e9;
int n,q,x[N+1];
ll query(ll s){
int l,r;
l=lower_bound(x+1,x+n+1,s)-x;
l=min(l,n);
if(l-1&&s-x[l-1]<=x[l]-s){
l--;
}
ll ans=abs(x[l]-s);
r=l;
bool mode=true;//1:向左,0:向右
while(1<l&&r<n){
if(mode){
int pl=x[r+1]-x[l];
int p=lower_bound(x+1,x+n+1,x[l]-pl)-x;
if(p<l){
ans+=x[l]-x[p];
l=p;
}else{
ans+=pl;
r++;
mode=!mode;
}
}else{
int pl=x[r]-x[l-1];
int p=lower_bound(x+1,x+n+1,x[r]+pl)-x-1;
if(r<p){
ans+=x[p]-x[r];
r=p;
}else{
ans+=pl;
l--;
mode=!mode;
}
}
}
ans+=x[n]-x[1];
return ans;
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i];
}
cin>>q;
for(int i=1;i<=q;i++){
ll s;
cin>>s;
cout<<query(s)<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
