CF1690C Restoring the Duration of Tasks

最近，Polycarp 完成了 $n$ 个连续的任务。 对于每个已完成的任务，已知任务被分配的时间 $s_i$（没有两个任务在同一时刻被分配）。还给出了任务完成的时间 $f_i$。对于每个任务，有一个未知值 $d_i$（$d_i>0$），表示任务的执行时长。 已知任务按照它们到达的顺序被完成。Polycarp 执行任务的方式如下： - 一旦第一个任务到来，Polycarp 立即开始执行它。 - 如果在 Polycarp 尚未完成前一个任务时有新任务到来，他会把新任务放到队列的末尾。 - 当 Polycarp 完成当前任务且队列不为空时，他会立即从队列头部取出下一个任务继续执行（如果队列为空，他就等待下一个任务到来）。 请你求出每个任务的 $d_i$（即每个任务的执行时长）。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来是每个测试用例的数据描述。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 每个测试用例的第二行包含 $n$ 个正整数 $s_1 < s_2 < \dots < s_n$（$0 \le s_i \le 10^9$），表示每个任务被分配的时间。 每个测试用例的第三行包含 $n$ 个正整数 $f_1 < f_2 < \dots < f_n$（$s_i < f_i \le 10^9$），表示每个任务完成的时间。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一行 $n$ 个正整数 $d_1, d_2, \dots, d_n$，表示每个任务的执行时长。

第一个测试用例： 一开始队列为空：$[\,]$。此时第一个任务到来。Polycarp 在时间 $2$ 完成第一个任务，因此第一个任务的执行时长为 $2$。队列为空，Polycarp 继续等待。 在时间 $3$，第二个任务到来。在时间 $7$，第三个任务到来，此时队列为 $[7]$。 在时间 $10$，Polycarp 完成第二个任务，因此第二个任务的执行时长为 $7$。 在时间 $10$，Polycarp 立即开始第三个任务，并在时间 $11$ 完成。因此第三个任务的执行时长为 $1$。  这是第一个测试用例的示意图。 由 ChatGPT 4.1 翻译