← 返回题目列表

AtCoder · joig2026final_e

E. 铁路之旅4

中文机器翻译题面 查看原题

配点 : 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).
  • 所有输入值都是整数。

小課題

  1. (8 点) K \leqq 2.
  2. (11 点) N \leqq 500.
  3. (29 点) Q = 1.
  4. (20 点) K \leqq 5.
  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 满足约束。