CF1807G2 Subsequence Addition (Hard Version)

本题与原版本唯一的区别在于，本题的约束条件更高。 初始时，数组 $a$ 仅包含数字 $1$。你可以进行若干次操作来改变该数组。在每次操作中，你可以选择 $a$ 的某个子序列 $^{\dagger}$，并将该子序列所有元素之和作为一个新元素加入到 $a$ 中。 现在给定一个最终数组 $c$，请判断是否可以通过对初始数组 $a$ 进行若干次（可以为 $0$ 次）上述操作后得到数组 $c$。 $^{\dagger}$ 序列 $b$ 是序列 $a$ 的一个子序列，如果 $b$ 可以通过从 $a$ 中删除若干（可以为零，但不能全部）元素得到。换句话说，就是选择 $k$ 个（$1 \leq k \leq |a|$）不同的下标 $i_1, i_2, \dots, i_k$，并在 $a$ 的任意位置插入一个新元素，其值为 $a_{i_1} + a_{i_2} + \dots + a_{i_k}$。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示最终数组 $c$ 的元素个数。 每个测试用例的第二行包含 $n$ 个用空格分隔的整数 $c_i$（$1 \leq c_i \leq 2 \cdot 10^5$），表示最终数组 $c$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果存在这样一系列操作可以得到数组 $c$，输出 "YES"（不带引号）；否则输出 "NO"（不带引号）。 你可以以任意大小写输出答案（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为正解）。

对于第一个测试用例，初始数组 $a$ 已经等于 $[1]$，所以答案是 "YES"。 对于第二个测试用例，无论进行多少次操作，$a$ 都会变成至少包含两个元素的数组，且不会只包含元素 $2$，因此无法得到数组 $[2]$，答案是 "NO"。 对于第三个测试用例，可以按如下操作得到最终数组 $c$： - 初始时，$a = [1]$。 - 选择子序列 $[1]$，插入 $1$，$a$ 变为 $[1, 1]$。 - 选择子序列 $[1, 1]$，插入 $1+1=2$，$a$ 变为 $[1, 2, 1]$。 - 选择子序列 $[1, 2]$，插入 $1+2=3$，$a$ 变为 $[1, 3, 2, 1]$。 - 选择子序列 $[1, 3, 1]$，插入 $1+3+1=5$，$a$ 变为 $[5, 1, 3, 2, 1]$（这就是我们需要得到的数组）。 由 ChatGPT 4.1 翻译