配点 : 100 点
問題文
在罗马的某个郊区,1 有足够长的轨道。这条轨迹可以被认为是一条数轴,沿着轨迹的每个点都是 由 1 整数的坐标表示。 沿着这条线 有 N 站,按坐标递减顺序排列。 它们的编号最大为 1 减去 N 。车站 i (1 \leqq i \leqq N) 的位置是坐标 A_i 。2 同一坐标上永远不能有多个站点。
火车正在这条轨道上行驶。列车仅沿从小坐标点到大坐标点的方向运行,并在所有车站停靠。
票价根据上车站和下车站之间的距离确定,并由一定的整数序列确定。 使用 (B_1, B_2, ..., B_K) 计算如下。在这里,1 = B_1 < B_2 < \cdots < B_K 成立。请注意,上车车站和下车车站必须不同。
- 上车站与下车站距离 d (d\geqq 1)和 满足B_j \leqq d 的最大整数 j (1 \leqq j \leqq K) j_\text{max} 。此时票价为 j_\text{max} 。
来意大利观光的Bitaro登上了这趟列车。 Q 我计划多次乘坐火车,并且想计算每次行程的票价。 k 回目 (1 \leqq k \leqq Q) 乘车计划包括上车和前往车站。 l_k 从车站 r_k 。在这里,l_k < r_k 。
Bitaro 很累,所以他不乘坐火车或在车站之间移动。不过,您可以在火车中途下车,支付一次车费,然后从该站再次上车。 您可以在任何车站下车,并且下车次数没有限制。 例如,车站 如果您在 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} 的票价。
Bitaro正确下车即可在车站下车。 我想最小化前往 l_k 从车站 r_k 所需的总票价。
给定有关车站、票价和登机计划的信息,编写一个程序,找出 Bitaro 必须为每个登机计划支付的总票价的最小值。
入力
输入是按以下格式从标准输入给出的。
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 \leqq k \leqq Q) 是 写入 k 输出 Bitaro 第一次乘车计划需要支付的总票价的最小值。
制約
- 2 \leqq N \leqq 150\,000.
- 1 \leqq A_1 < A_2 < \cdots < A_N \leqq 10^9.
- 1 \leqq K \leqq 20.
- 1 = B_1 < B_2 < \cdots < B_K \leqq 10^9.
- 1 \leqq Q \leqq 150\,000.
- 1 \leqq l_k < r_k \leqq N (1 \leqq k \leqq Q).
- 所有输入值都是整数。
小課題
- (8 点) K \leqq 2.
- (11 点) N \leqq 500.
- (29 点) Q = 1.
- (20 点) K \leqq 5.
- (32 点)没有额外的限制。
入力例 1
8 1 3 4 5 8 9 12 14 8 1 2 5 6 7 9 10 11 3 1 5 3 5 1 7
出力例 1
4 2 6
1 在第一个乘车计划中,Bitaro 上车并停在车站。 我想去 l_1=1 从车站 r_1=5 。 此时,您可以例如执行以下操作。
- 一、站 1 并在车站上车。 在 3 下车。此时的行驶距离为 A_3 - A_1 = 3 和B_j \leqq 3 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
- 接下来,站 在 3 再次登上火车并前往车站。 在 5 下车。此时的行驶距离为 A_5 - A_3 = 4 和B_j \leqq 4 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
本例中的总票价为 2 + 2 = 4 ,并且总票价不能小于此。因此, 在1 线 4 。 你只需要砍掉
2 在第一个乘车计划中,Bitaro 上车并停在车站。 我想去 l_2=3 从车站 r_2=5 。 此时,您可以例如执行以下操作。
- 駅 3 并在车站上车。 在 5 下车。此时的行驶距离为 A_5 - A_3 = 4 和B_j \leqq 4 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
本例中的总票价为 2 ,并且总票价不能小于此。因此, 在2 线 2 。 你只需要砍掉
3 在第一个乘车计划中,Bitaro 上车并停在车站。 我想去 l_3=1 从车站 r_3=7 。 此时,您可以例如执行以下操作。
- 一、站 1 并在车站上车。 在 4 下车。此时的行驶距离为 A_4 - A_1 = 4 和B_j \leqq 4 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
- 接下来,站 在 4 再次登上火车并前往车站。 在 6 下车。此时的行驶距离为 A_6 - A_4 = 4 和B_j \leqq 4 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
- 接下来,站 在 6 再次登上火车并前往车站。 在 7 下车。此时的行驶距离为 A_7 - A_6 = 3 和B_j \leqq 3 的最大整数 j (1 \leqq j \leqq K) 是 2 ,所以票价是 2 。
本例中的总票价为 2 + 2 + 2 = 6 ,并且总票价不能小于此。因此, 在3 线 6 。 你只需要砍掉
此输入示例是一个小作业。 2,5 满足约束。
入力例 2
10 3 6 16 19 32 40 41 53 59 78 2 1 15 1 3 10
出力例 2
2
此输入示例满足所有子任务约束。
入力例 3
10 11 13 39 42 53 54 66 69 77 83 15 1 5 13 31 40 41 52 57 59 66 70 79 97 103 115 5 1 6 2 9 1 8 2 7 3 9
出力例 3
6 7 6 6 4
此输入示例是一个小作业。 2,5 满足约束。