310271: CF1807G2. Subsequence Addition (Hard Version)
Description
The only difference between the two versions is that in this version, the constraints are higher.
Initially, array $a$ contains just the number $1$. You can perform several operations in order to change the array. In an operation, you can select some subsequence$^{\dagger}$ of $a$ and add into $a$ an element equal to the sum of all elements of the subsequence.
You are given a final array $c$. Check if $c$ can be obtained from the initial array $a$ by performing some number (possibly 0) of operations on the initial array.
$^{\dagger}$ A sequence $b$ is a subsequence of a sequence $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly zero, but not all) elements. In other words, select $k$ ($1 \leq k \leq |a|$) distinct indices $i_1, i_2, \dots, i_k$ and insert anywhere into $a$ a new element with the value equal to $a_{i_1} + a_{i_2} + \dots + a_{i_k}$.
InputThe first line of the input contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of elements the final array $c$ should have.
The second line of each test case contains $n$ space-separated integers $c_i$ ($1 \leq c_i \leq 2 \cdot 10^5$) — the elements of the final array $c$ that should be obtained from the initial array $a$.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
OutputFor each test case, output "YES" (without quotes) if such a sequence of operations exists, and "NO" (without quotes) otherwise.
You can output the answer in any case (for example, the strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive answer).
ExampleInput6 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 1Output
YES NO YES NO YES YESNote
For the first test case, the initial array $a$ is already equal to $[1]$, so the answer is "YES".
For the second test case, performing any amount of operations will change $a$ to an array of size at least two which doesn't only have the element $2$, thus obtaining the array $[2]$ is impossible and the answer is "NO".
For the third test case, we can perform the following operations in order to obtain the final given array $c$:
- Initially, $a = [1]$.
- By choosing the subsequence $[1]$, and inserting $1$ in the array, $a$ changes to $[1, 1]$.
- By choosing the subsequence $[1, 1]$, and inserting $1+1=2$ in the middle of the array, $a$ changes to $[1, 2, 1]$.
- By choosing the subsequence $[1, 2]$, and inserting $1+2=3$ after the first $1$ of the array, $a$ changes to $[1, 3, 2, 1]$.
- By choosing the subsequence $[1, 3, 1]$ and inserting $1+3+1=5$ at the beginning of the array, $a$ changes to $[5, 1, 3, 2, 1]$ (which is the array we needed to obtain).
Input
题意翻译
本题为困难版,两题的唯一区别在于数据范围的大小。 数列 $a$ 最开始只有一个数 $1$,你可以进行若干次操作,每次操作你可以选取 $k$ 个数($k$ 无限制,小于等于 $a$ 的大小即可),将这 $k$ 个数的和放入 $a$ 的任意一个位置。 给定一个长度为 $n$ 的序列 $c$,问 $a$ 能否在进行若干次操作后转为 $c$。 有 $t$ 组数据。 $1\leq n\leq2\times10^5,1\leq c_i\leq2\times10^5,1\leq t\leq1000$ by @[Larryyu](https://www.luogu.com.cn/user/475329)Output
这个题目是“子序列加法”的困难版本,与简单版本唯一的不同在于这个版本的限制条件更高。
最初,数组 $ a $ 只包含数字 $ 1 $。你可以执行几个操作来改变数组。在一次操作中,你可以选择 $ a $ 的某个子序列,并向 $ a $ 中添加一个等于子序列所有元素和的新元素。
给你一个最终数组 $ c $。检查是否可以通过对初始数组 $ a $ 执行若干次(可能为 0 次)操作来从初始数组得到数组 $ c $。
输入输出数据格式:
输入:
第一行包含一个整数 $ 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 $),表示应该从初始数组 $ a $ 得到的最终数组 $ c $ 的元素。
保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。
输出:
对于每个测试用例,如果存在这样的操作序列,输出 "YES"(不包含引号),否则输出 "NO"(不包含引号)。
你可以以任何大小写形式输出答案,例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。题目大意: 这个题目是“子序列加法”的困难版本,与简单版本唯一的不同在于这个版本的限制条件更高。 最初,数组 $ a $ 只包含数字 $ 1 $。你可以执行几个操作来改变数组。在一次操作中,你可以选择 $ a $ 的某个子序列,并向 $ a $ 中添加一个等于子序列所有元素和的新元素。 给你一个最终数组 $ c $。检查是否可以通过对初始数组 $ a $ 执行若干次(可能为 0 次)操作来从初始数组得到数组 $ c $。 输入输出数据格式: 输入: 第一行包含一个整数 $ 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 $),表示应该从初始数组 $ a $ 得到的最终数组 $ c $ 的元素。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $。 输出: 对于每个测试用例,如果存在这样的操作序列,输出 "YES"(不包含引号),否则输出 "NO"(不包含引号)。 你可以以任何大小写形式输出答案,例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定的回答。