1011. Push Box

题目描述

数轴上有若干个带编号的箱子。第 $i$ 个箱子的初始位置是整数 $a_i$，它需要在某个时刻到达过整数位置 $b_i$，最后仍然回到并停留在 $a_i$。

一次操作中，你可以选择一个箱子，将它向左或向右移动 $1$ 个单位。任意时刻任意两个箱子都不能位于同一个整数位置。箱子可以被移动到负数位置。

对于每个 $m=1,2,\ldots,n$，只考虑编号 $1$ 到 $m$ 的箱子。你需要求出：使这 $m$ 个箱子都到达过各自的目标位置，并且最终全部回到初始位置的最少操作次数。

如果 $a_i=b_i$，则第 $i$ 个箱子在初始时刻就已经到达过目标位置。

输入格式

第一行包含一个整数 $T$（$1\le T\le 10^2$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$）。
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^9$），表示箱子的初始位置。
• 第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1\le b_i\le 10^9$），表示箱子的目标位置。

保证同一组测试数据内 $a_1,a_2,\ldots,a_n$ 两两不同，且所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行 $n$ 个整数。第 $m$ 个整数表示只考虑编号 $1$ 到 $m$ 的箱子时的最少操作次数。

答案可能为 $0$，并且可能超过 $32$ 位整数范围。

样例输入

2
2
2 3
3 1
3
2 1 4
3 1 2

样例输出

2 12
2 2 10

提示

第一组测试用例中，当 $m=2$ 时，一种最优方案如下：

1. 将第 $2$ 个箱子从 $3$ 移动到 $4$；
2. 将第 $1$ 个箱子从 $2$ 移动到 $3$；
3. 将第 $1$ 个箱子从 $3$ 移动到 $0$；
4. 将第 $2$ 个箱子从 $4$ 移动到 $1$；
5. 将第 $2$ 个箱子从 $1$ 移动到 $3$；
6. 将第 $1$ 个箱子从 $0$ 移动到 $2$。

总操作次数为 $1+1+3+3+2+2=12$。

来源：2026杭电多校-测试专用（山西实验） 原题链接：http://acm.hdu.edu.cn/contest/problem_show.php?cid=1234&pid=1011