题目描述

本题与原版本唯一的区别在于，本题的约束条件更高。

初始时，数组 $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" 都会被识别为正解）。

样例

6
1
1
1
2
5
5 1 3 2 1
5
7 1 5 2 1
3
1 1 1
5
1 1 4 2 1

YES
NO
YES
NO
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 翻译

来源

Codeforces 1807G2，英文题名 Subsequence Addition (Hard Version)。