CF1914E2.Game with Marbles (Hard Version)

The easy and hard versions of this problem differ only in the constraints on the number of test cases and $n$. In the hard version, the number of test cases does not exceed $10^4$, and the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$. Furthermore, there are no additional constraints on $n$ in a single test case.

Recently, Alice and Bob were given marbles of $n$ different colors by their parents. Alice has received $a_1$ marbles of color $1$, $a_2$ marbles of color $2$,..., $a_n$ marbles of color $n$. Bob has received $b_1$ marbles of color $1$, $b_2$ marbles of color $2$, ..., $b_n$ marbles of color $n$. All $a_i$ and $b_i$ are between $1$ and $10^9$.

After some discussion, Alice and Bob came up with the following game: players take turns, starting with Alice. On their turn, a player chooses a color $i$ such that both players have at least one marble of that color. The player then discards one marble of color $i$, and their opponent discards all marbles of color $i$. The game ends when there is no color $i$ such that both players have at least one marble of that color.

The score in the game is the difference between the number of remaining marbles that Alice has and the number of remaining marbles that Bob has at the end of the game. In other words, the score in the game is equal to $(A-B)$, where $A$ is the number of marbles Alice has and $B$ is the number of marbles Bob has at the end of the game. Alice wants to maximize the score, while Bob wants to minimize it.

Calculate the score at the end of the game if both players play optimally.

本题的简单版本与困难版本仅在测试用例数量和 $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$，满足双方均至少拥有一颗该颜色的弹珠；然后，该玩家丢弃一颗颜色 $i$ 的弹珠，而其对手则丢弃所有颜色 $i$ 的弹珠。当不存在任何颜色 $i$ 满足双方均至少拥有一颗该颜色弹珠时，游戏结束。

游戏的得分为游戏结束时 Alice 剩余弹珠数与 Bob 剩余弹珠数之差，即得分为 $(A - B)$，其中 $A$ 表示游戏结束时 Alice 所拥有的弹珠数，$B$ 表示 Bob 所拥有的弹珠数。Alice 希望最大化该得分，而 Bob 希望最小化该得分。

若双方均以最优策略进行游戏，请计算游戏结束时的得分。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

Each test case consists of three lines:

• the first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of colors;
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), where $a_i$ is the number of marbles of the $i$-th color that Alice has;
• the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^9$), where $b_i$ is the number of marbles of the $i$-th color that Bob has.

Additional constraint on the input: the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$），其中 $a_i$ 表示爱丽丝拥有的第 $i$ 种颜色的弹珠数量；
• 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$），其中 $b_i$ 表示鲍勃拥有的第 $i$ 种颜色的弹珠数量。

输入的额外约束：所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the score at the end of the game if both Alice and Bob act optimally.

对于每个测试用例，输出一个整数——即在 Alice 和 Bob 均采取最优策略的情况下，游戏结束时的得分。

In the first example, one way to achieve a score of $1$ is as follows:

1. Alice chooses color $1$, discards $1$ marble. Bob also discards $1$ marble;
2. Bob chooses color $3$, discards $1$ marble. Alice also discards $1$ marble;
3. Alice chooses color $2$, discards $1$ marble, and Bob discards $2$ marble.

As a result, Alice has $a = [3, 1, 0]$ remaining, and Bob has $b = [0, 0, 3]$ remaining. The score is $3 + 1 - 3 = 1$.

It can be shown that neither Alice nor Bob can achieve a better score if both play optimally.

In the second example, Alice can first choose color $1$, then Bob will choose color $4$, after which Alice will choose color $2$, and Bob will choose color $3$. It can be shown that this is the optimal game.

在第一个例子中，一种得到分数 $1$ 的方法如下：

1. 爱丽丝选择颜色 $1$，丢弃 $1$ 颗弹珠；鲍勃也丢弃 $1$ 颗弹珠；
2. 鲍勃选择颜色 $3$，丢弃 $1$ 颗弹珠；爱丽丝也丢弃 $1$ 颗弹珠；
3. 爱丽丝选择颜色 $2$，丢弃 $1$ 颗弹珠，而鲍勃丢弃 $2$ 颗弹珠。

最终，爱丽丝剩余的弹珠为 $a = [3, 1, 0]$，鲍勃剩余的弹珠为 $b = [0, 0, 3]$。得分为 $3 + 1 - 3 = 1$。

可以证明：若双方均采取最优策略，则谁也无法获得高于 $1$ 的分数。

在第二个例子中，爱丽丝可首先选择颜色 $1$，随后鲍勃将选择颜色 $4$，接着爱丽丝选择颜色 $2$，鲍勃再选择颜色 $3$。可以证明，这是最优的游戏过程。