← 返回题目列表

Codeforces · 1605/E

E. 阵列均衡器

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

Jeevan 有两个数组 $$$a$$$ 和 $$$b$$$,大小为 $$$n$$$。他喜欢对数组执行奇怪的操作。这次,他提出了两种操作:

- 选择任意 $$$i$$$ ($$$1 \le i \le n$$$) 并为每个 $$$j$$$ 将 $$$a_j$$$ 增加 $$$1$$$,$$$j$$$ 是 $$$i$$$ 和 $$$1 \le j \le n$$$ 的倍数。
- 选择任意 $$$i$$$ ($$$1 \le i \le n$$$) 并为每个 $$$j$$$ 将 $$$a_j$$$ 递减 $$$1$$$,$$$j$$$ 是 $$$i$$$ 和 $$$1 \le j \le n$$$ 的倍数。

他想使用最少的总操作次数将数组 $$$a$$$ 转换为数组 $$$b$$$。然而,Jeevan 似乎忘记了 $$$b_1$$$ 的值。所以他做出了一些猜测。他会问你 $$$q$$$ 与他的 $$$q$$$ 猜测相对应的问题,其中第 $$$i$$$ 的形式如下:

- 如果 $$$b_1 = x_i$$$,将 $$$a$$$ 转换为 $$$b$$$ 所需的最少操作次数是多少?

回答每个问题来帮助他。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — 数组 $$$a$$$ 和 $$$b$$$ 的大小。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^6)$$$。

第三行包含$$$n$$$整数$$$b_1, b_2, ..., b_n$$$ $$$(1 \le b_i \le 10^6$$$ for $$$i \neq 1$$$; $$$b_1 = -1$$$,表示$$$b_1$$$的值未知$$$)$$$。

第四行包含一个整数 $$$q$$$ $$$(1 \le q \le 2 \cdot 10^{5})$$$ — 问题数。

以下 $$$q$$$ 行中的每一行都包含一个整数 $$$x_i$$$ $$$(1 \le x_i \le 10^6)$$$ — 代表第 $$$i$$$ 问题。

输出

输出 $$$q$$$ 整数 — 每个 $$$q$$$ 问题的答案。

示例

输入 #1

2
3 7
-1 5
3
1
4
3

输出 #1

2
4
2

输入 #2

6
2 5 4 1 3 6
-1 4 6 2 3 5
3
1
8
4

输出 #2

10
29
9

注意

考虑第一个测试用例。

- $$$b_1 = 1$$$: 我们需要转换 $$$[3, 7] \rightarrow [1, 5]$$$。我们可以执行以下操作:$$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 1}}$$$ $$$[2, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 1}}$$$ $$$[1, 5]$$$因此答案是$$$2$$$。
- $$$b_1 = 4$$$:我们需要转换 $$$[3, 7] \rightarrow [4, 5]$$$。我们可以执行以下操作: $$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 5]$$$ $$$\xrightarrow[\text{增加}]{\text{i = 1}}$$$ $$$[4, 6]$$$ $$$\xrightarrow[\text{减少}]{\text{i = 2}}$$$ $$$[4, 5]$$$因此答案是$$$4$$$。
- $$$b_1 = 3$$$:我们需要转换 $$$[3, 7] \rightarrow [3, 5]$$$。我们可以执行以下操作:$$$[3, 7]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 6]$$$ $$$\xrightarrow[\text{decrease}]{\text{i = 2}}$$$ $$$[3, 5]$$$因此答案是$$$2$$$。