[AdditionalFile5368.zip](file://AdditionalFile5368.zip?type=additional_file)

#5368. 「OOI 2024 Day 2」几乎确定

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2024 Day2 T4 「Почти наверное / Almost Certainly」。

我们说两个多重集几乎确定相等，如果它们在至多一个元素上有所不同。也就是说，可以通过最多修改第一个多重集中的一个元素使两者相等。例如，多重集 $\{1, 1, 2\}$ 和 $\{1, 2, 3\}$ 是几乎确定相等的，$\{1, 1, 1\}$ 和 $\{1, 1, 1\}$ 是几乎确定相等的，而 $\{1, 2, 3\}$ 和 $\{3, 4, 5\}$ 不是几乎确定相等的。

小男孩瓦西娅非常喜欢这个定义，并立即想出了一个相关问题。

瓦西娅有两个数组 $a$ 和 $b$，且对于所有 $i$ 从 $1$ 到 $n$，都有 $a_i \ge b_i$。瓦西娅可以对数组 $a$ 进行任意多次（包括零次）以下操作：选择任意编号 $i$ $(1 \le i \le n)$，将 $a_i$ 减去 $1$。数组 $b$ 保持不变。

瓦西娅很快明白了如何通过一系列操作使得数组 $a$ 和 $b$ 的多重集值几乎确定相等。因此，他将问题复杂化——现在他希望对这两个数组的每个前缀，了解需要应用的最小操作次数，使得前缀的数组值几乎确定相等。

更正式地说，对于从 $1$ 到 $n$ 的每个 $k$，瓦西娅希望取数组 $a$ 的前 $k$ 个元素 $a_1, a_2, \ldots, a_k$ 和数组 $b$ 的前 $k$ 个元素 $b_1, b_2, \ldots, b_k$。他想知道需要进行的最小操作次数，使得这两个前缀的多重集几乎确定相等。注意，每个 $k$ 的问题独立解决。

输入格式

每个测试点包含一个或多个输入数据组。第一行包含一个整数 $t$ $(1 \le t \le 100000)$，表示输入数据组的数量。接下来是各组数据的描述。

每组数据的第一行包含一个整数 $n$ $(1 \le n \le 200000)$，表示数组 $a$ 和 $b$ 的大小。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \le a_i \le 10^{9})$，表示数组 $a$ 的元素。

第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$ $(1 \le b_i \le a_i)$，表示数组 $b$ 的元素。

设 $N$ 为所有数据组中 $n$ 的总和。保证 $N \le 200000$。

输出格式

对于每组输入数据，输出 $n$ 个数字，每个数字表示对每个可能的前缀长度解决问题的答案。可以证明，答案始终存在。

样例 1

输入

4
2
3 4
1 2
2
3 4
1 3
3
11 17 14
1 13 10
4
100 11 50 42
30 1 20 5

输出

0 1
0 0
0 4 2
0 10 30 48

考虑第一个样例中的第一组输入数据：

• 对于长度为 $1$ 的前缀，无需操作。
• 对于长度为 $2$ 的前缀，需要将 $a_1 = 3$ 减少 $1$ 次，之后 $a$ 为 $[2, 4]$，$b$ 为 $[1, 2]$，两者几乎确定相等。

考虑第一个样例中的第三组输入数据：

• 对于长度为 $1$ 的前缀，无需操作。
• 对于长度为 $2$ 的前缀，需要将 $a_2 = 17$ 减少 $4$ 次，之后前缀 $a$ 为 $[11, 13]$，前缀 $b$ 为 $[1, 13]$，两者几乎确定相等。
• 对于长度为 $3$ 的前缀，需要将 $a_1 = 11$ 减少 $1$ 次，将 $a_3 = 14$ 减少 $1$ 次，之后 $a$ 为 $[10, 17, 13]$，$b$ 为 $[1, 13, 11]$，两者几乎确定相等。

样例 2

输入

3
4
2 4 5 12
1 3 4 10
4
3 5 8 20
1 2 6 7
4
4 4 4 4
1 2 3 4

输出

0 1 1 3
0 1 3 6
0 2 3 3

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。