AT_joig2026final_e 鉄道旅行 4 (Railway Trip 4)

在罗马的某个郊区，有一条足够长的铁路，可以看作是一条数轴。沿着铁路的每个地点可以用一个整数坐标表示。这条铁路上有 $N$ 个车站，按坐标从小到大编号为 $1$ 到 $N$。第 $i$ 个车站（$1 \leq i \leq N$）的位置是坐标 $A_i$。没有两个及以上车站在同一个坐标上。 有一列火车在这条铁路上运行，只沿着坐标小的地方向坐标大的地方行驶，并且会停靠所有车站。 票价取决于上车站和下车站之间的距离，计算公式如下，基于一个整数列 $(B_1, B_2, ..., B_K)$，满足 $1 = B_1 < B_2 < \cdots < B_K$。注意，上车站和下车站必须不同。 - 设上车站与下车站的距离为 $d$（$d \geq 1$），找到满足 $B_j \leq d$ 的最大整数 $j$（$1 \leq j \leq K$），记为 $j_\text{max}$。此次乘车的票价为 $j_\text{max}$。 比太郎来到意大利旅游，计划乘坐这列火车共 $Q$ 次，并想计算每次乘车的票价。他的第 $k$ 次乘坐（$1 \leq k \leq Q$）计划为从第 $l_k$ 号站乘车到第 $r_k$ 号站，这里 $l_k < r_k$。 比太郎很累，不会选择未乘坐火车在车站间移动。但是，他可以在任意车站中途下车以结算票价，然后再从该车站重新上车。中途下车次数不限。在第 $s_1, s_2, \cdots, s_m$ 站中途下车（$l_k < s_1 < s_2 < \cdots < s_m < r_k$）时，他需要为以下距离分别支付票价：$A_{s_1} - A_{l_k},\ A_{s_2} - A_{s_1},\ A_{s_3} - A_{s_2},\ \cdots,\ A_{s_m} - A_{s_{m-1}},\ A_{r_k} - A_{s_m}$。 比太郎想要合理选择中途下车的方式，以使得从 $l_k$ 站到 $r_k$ 站所需支付的票价总和最小。 现已给出车站、票价以及乘车计划的信息，请编程计算对于每个乘车计划，比太郎需要支付的最小票价总和。

输入将以如下格式从标准输入给出。 > $N\ A_1\ A_2\ \cdots\ A_N\ K\ B_1\ B_2\ \cdots\ B_K\ Q\ l_1\ r_1\ l_2\ r_2\ \vdots\ l_Q\ r_Q$

请输出 $Q$ 行。第 $k$ 行（$1 \leq k \leq Q$）输出比太郎第 $k$ 次乘车计划需要支付的最小票价总和。

## 子任务 1.（8分）$K \leq 2$。 2.（11分）$N \leq 500$。 3.（29分）$Q = 1$。 4.（20分）$K \leq 5$。 5.（32分）无额外限制。 --- ## 样例解释 1 在第 $1$ 次乘车计划中，比太郎需要从 $l_1=1$ 号站乘车到 $r_1=5$ 号站。他的行动可以如以下所示： - 首先从第 $1$ 号站上车，在第 $3$ 号站中途下车，此时乘车距离为 $A_3-A_1=3$，满足 $B_j \leq 3$ 的最大 $j$（$1 \leq j \leq K$）为 $2$，因此票价为 $2$。 - 然后在第 $3$ 号站重新上车，在第 $5$ 号站下车，此时乘车距离为 $A_5-A_3=4$，满足 $B_j \leq 4$ 的最大 $j$（$1 \leq j \leq K$）为 $2$，因此票价为 $2$。 上述情况下票价总和为 $2 + 2 = 4$，无法再更小，因此第 $1$ 行输出 $4$。 在第 $2$ 次乘车计划中，比太郎需要从 $l_2=3$ 号站乘车到 $r_2=5$ 号站。他可以如下行动： - 在第 $3$ 号站上车，在第 $5$ 号站下车，乘车距离为 $A_5-A_3=4$，满足 $B_j \leq 4$ 的最大 $j$ 为 $2$，因此票价为 $2$。 此时票价总和为 $2$，无法再更小，因此第 $2$ 行输出 $2$。 在第 $3$ 次乘车计划中，比太郎需要从 $l_3=1$ 号站乘车到 $r_3=7$ 号站。可以如下行动： - 首先从第 $1$ 号站上车在第 $4$ 号站中途下车，乘车距离为 $A_4-A_1=4$，满足 $B_j \leq 4$ 的最大 $j$ 为 $2$，票价为 $2$。 - 然后从第 $4$ 号站上车在第 $6$ 号站中途下车，乘车距离为 $A_6-A_4=4$，满足 $B_j \leq 4$ 的最大 $j$ 为 $2$，票价为 $2$。 - 然后从第 $6$ 号站上车在第 $7$ 号站下车，乘车距离为 $A_7-A_6=3$，满足 $B_j \leq 3$ 的最大 $j$ 为 $2$，票价为 $2$。 此时票价总和为 $2 + 2 + 2 = 6$，无法再更小，因此第 $3$ 行输出 $6$。 该输入样例满足子任务 $2,5$ 的限制。 --- ## 样例解释 2 该输入样例满足所有子任务的限制。 --- ## 样例解释 3 该输入样例满足子任务 $2,5$ 的限制。 # 约束条件 - $2 \leq N \leq 150\,000$。 - $1 \leq A_1 < A_2 < \cdots < A_N \leq 10^9$。 - $1 \leq K \leq 20$。 - $1 = B_1 < B_2 < \cdots < B_K \leq 10^9$。 - $1 \leq Q \leq 150\,000$。 - $1 \leq l_k < r_k \leq N$（$1 \leq k \leq Q$）。 - 所有输入均为整数。 由 ChatGPT 5 翻译