CF1914E2 Game with Marbles (Hard Version)

本题的简单版与困难版的区别仅在于测试用例数量和 $n$ 的限制。在困难版中，测试用例数量不超过 $10^4$，所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。此外，单个测试用例中的 $n$ 没有额外限制。 最近，Alice 和 Bob 的父母给了他们 $n$ 种不同颜色的弹珠。Alice 拥有第 $1$ 种颜色的 $a_1$ 个弹珠，第 $2$ 种颜色的 $a_2$ 个弹珠，……，第 $n$ 种颜色的 $a_n$ 个弹珠。Bob 拥有第 $1$ 种颜色的 $b_1$ 个弹珠，第 $2$ 种颜色的 $b_2$ 个弹珠，……，第 $n$ 种颜色的 $b_n$ 个弹珠。所有 $a_i$ 和 $b_i$ 的取值范围为 $1$ 到 $10^9$。 经过一番讨论，Alice 和 Bob 想出了如下的游戏规则：两人轮流操作，Alice 先手。在每一回合，当前玩家选择一种颜色 $i$，要求两人手中该颜色的弹珠都至少有一个。然后，该玩家丢弃自己手中一种该颜色的弹珠 $1$ 个，对手则丢弃所有该颜色的弹珠。游戏结束的条件是不存在某种颜色 $i$，使得两人手中该颜色的弹珠都至少有一个。 游戏的得分为游戏结束时 Alice 剩余弹珠数减去 Bob 剩余弹珠数，即 $A-B$，其中 $A$ 为 Alice 剩余弹珠数，$B$ 为 Bob 剩余弹珠数。Alice 希望最大化得分，Bob 希望最小化得分。 请计算当双方都采取最优策略时，游戏结束时的得分。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含三行： - 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示颜色的数量； - 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示 Alice 拥有的每种颜色的弹珠数量； - 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$），表示 Bob 拥有的每种颜色的弹珠数量。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示当 Alice 和 Bob 都采取最优策略时，游戏结束时的得分。

在第一个样例中，一种得到得分 $1$ 的方案如下： 1. Alice 选择颜色 $1$，丢弃 $1$ 个弹珠，Bob 也丢弃 $1$ 个弹珠； 2. Bob 选择颜色 $3$，丢弃 $1$ 个弹珠，Alice 也丢弃 $1$ 个弹珠； 3. Alice 选择颜色 $2$，丢弃 $1$ 个弹珠，Bob 丢弃 $2$ 个弹珠。 最终，Alice 剩余 $a = [3, 1, 0]$，Bob 剩余 $b = [0, 0, 3]$。得分为 $3 + 1 - 3 = 1$。 可以证明，如果双方都采取最优策略，得分无法更优。 在第二个样例中，Alice 可以先选择颜色 $1$，然后 Bob 选择颜色 $4$，之后 Alice 选择颜色 $2$，Bob 选择颜色 $3$。可以证明这是最优策略。 由 ChatGPT 4.1 翻译