P13509 [OOI 2024] Almost Certainly

我们称两个多重集**几乎等价**，如果它们至多有一个元素不同。也就是说，可以通过将第一个多重集中的**至多一个元素**修改为其他值，使得两个多重集完全相同。例如，多重集 $\{1, 1, 2\}$ 与 $\{1, 2, 3\}$ 是**几乎等价**的，$\{1, 1, 1\}$ 与 $\{1, 1, 1\}$ 也是**几乎等价**的，而 $\{1, 2, 3\}$ 与 $\{3, 4, 5\}$ 则不是**几乎等价**的。 有一个叫 Vasya 的男孩非常喜欢这个定义，并立刻想出了相关的问题。 Vasya 有两个数组 $a$ 和 $b$，且对于所有 $i$，都有 $a_i \geq b_i$。Vasya 可以对数组 $a$ 进行如下操作若干次（可以为零次）：选择任意一个下标 $i$（$1 \leq i \leq n$），并将 $a_i$ 减 $1$。数组 $b$ 不发生任何变化。 Vasya 很快就明白了如何通过一系列操作，使得数组 $a$ 和 $b$ 的值组成的多重集**几乎等价**。于是他将问题升级——现在，他想知道对于这两个数组的每一个前缀，最少需要多少次操作，才能使这两个前缀的多重集**几乎等价**。 更具体地说，对于每个 $k$，$1 \leq k \leq n$，Vasya 需要考虑 $a_1, a_2, \ldots, a_k$ 以及 $b_1, b_2, \ldots, b_k$ 这两个前缀，并求出最少需要多少次操作，才能使这两个前缀的多重集**几乎等价**。注意，每个 $k$ 的问题是**独立**解决的。

每组测试包含一个或多个数据集。第一行是一个整数 $t$（$1 \leq t \leq 100\,000$），表示数据集数量。接下来是每组数据集的描述。 每组数据集的第一行是一个整数 $n$（$1 \leq n \leq 200\,000$），表示数组 $a$ 和 $b$ 的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$ 的元素。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq a_i$），表示数组 $b$ 的元素。 设 $N$ 为所有数据集中 $n$ 的总和，保证 $N \leq 200\,000$。

对于每组数据集，输出 $n$ 个整数，分别表示每个前缀的答案。可以证明答案总是存在。

### 说明 以第一个输入样例的第一组数据为例： - 对于长度为 $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, 10]$，两者**几乎等价**。 ### 计分方式 本题共六组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。部分组不要求通过样例测试。**Offline-evaluation** 表示该组结果仅在赛后可见。 | 组别 | 分值 | 额外约束 | 依赖组 | 备注 | |:-----:|:------:|:----------------------:|:---------------:|:-------:| | 0 | 0 | -- | -- | 样例。 | | 1 | 16 | $N \leqslant 100$ | 0 | -- | | 2 | 13 | $N \leqslant 500$ | 0, 1 | -- | | 3 | 24 | $N \leqslant 3000$ | 0--2 | -- | | 4 | 13 | -- | -- | $a_i < b_{i + 1}$ | | 5 | 14 | -- | 4 | $a_i \leqslant a_{i + 1},\ b_i \leqslant b_{i + 1}$ | | 6 | 20 | -- | 0--5 | **Offline-evaluation.** | 翻译由 ChatGPT-4.1 完成。