CF1943E2 MEX Game 2 (Hard Version)

这是该问题的困难版本。两种版本的区别仅在于 $t$、$m$ 以及 $m$ 的总和的约束。只有在两种版本都被解决的情况下，你才能进行 hack。 Alice 和 Bob 又在一个长度为 $n$ 的数组 $a$ 上玩游戏。Alice 以一个空数组 $c$ 开始。两人轮流操作，Alice 先手。 在 Alice 的回合，她从 $a$ 中选择一个元素，将其添加到 $c$ 的末尾，并从 $a$ 中删除该元素。 在 Bob 的回合，他可以从 $a$ 中选择至多 $k$ 个元素，并将它们从 $a$ 中删除。 当数组 $a$ 为空时，游戏结束。Alice 的得分定义为 $c$ 的 MEX $^\dagger$。Alice 希望最大化她的得分，而 Bob 希望最小化它。如果两人都采取最优策略，求 Alice 的最终得分。 数组将以压缩格式给出。不会直接给出数组中的元素，而是给出它们的出现次数。具体来说，给定 $m$，即数组中的最大元素，然后给出 $m+1$ 个整数 $f_0, f_1, \ldots, f_m$，其中 $f_i$ 表示 $i$ 在数组 $a$ 中出现的次数。 $^\dagger$ 一个整数数组的 $\operatorname{MEX}$（最小不可达数）定义为不在该数组中出现的最小非负整数。例如： - $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 不在数组中。 - $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 在数组中，但 $2$ 不在。 - $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都在数组中，但 $4$ 不在。

每组测试包含多组数据。第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的数量。每组测试用例的描述如下。 每组测试用例的第一行包含两个整数 $m$ 和 $k$（$1 \le m \le 2 \cdot 10^5, 1 \le k \le 10^9$）。 第二行包含 $m+1$ 个整数 $f_0, f_1, \ldots, f_m$（$1 \le f_i \le 10^9$）。 保证所有测试用例中 $m$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试用例，如果双方都采取最优策略，输出 Alice 的得分。

在第一个测试用例中，数组 $a$ 为 $[0, 0, 0, 0, 1, 1, 1, 1, 1]$。一种得分为 $2$ 的可能游戏过程如下： 1. Alice 选择元素 $0$。此时 $a = [0, 0, 0, 1, 1, 1, 1, 1]$，$c=[0]$。 2. Bob 选择移除 $3$ 个元素 $0$、$0$ 和 $1$。此时 $a = [0, 1, 1, 1, 1]$，$c=[0]$。 3. Alice 选择元素 $1$。此时 $a = [0,1,1,1]$，$c=[0,1]$。 4. Bob 移除剩下的 $4$ 个元素 $0$、$1$、$1$ 和 $1$。此时 $a=[\,]$，$c=[0,1]$。 最后，$c=[0,1]$，其 MEX 为 $2$。注意，这只是一个示例过程，并不一定代表双方的最优策略。 在第二个测试用例中，Alice 可以在第一回合选择一个 $0$，保证她的得分至少为 $1$。而 Bob 可以在第一回合移除所有 $1$，从而保证 Alice 的得分不超过 $1$。因此，如果双方都采取最优策略，Alice 的得分为 $1$。 由 ChatGPT 4.1 翻译