# Subsequence Addition (Hard Version)
## 题面翻译
本题为困难版，两题的唯一区别在于数据范围的大小。
数列 $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)
## 题目描述
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} $ .
## 输入格式
The 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 $ .
## 输出格式
For 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).
## 样例 #1
### 样例输入 #1
```
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
```
### 样例输出 #1
```
YES
NO
YES
NO
YES
YES
```
## 提示
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).
//Subsequence Addition //只需要新添加的数小于前几个数的前缀和就可以了 #include <bits/stdc++.h> #define int long long using namespace std; const int N=1e6+10,mod=1e9+7; int s[N]; int n,t,a[N],f[N],res,num,ans,m; bool vis[N]; signed main() { std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>t; while(t--){ cin>>n; bool f=false; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+n+1); for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i]; if(s[1]!=1) f=true; for(int i=2;i<=n;i++) if(a[i]>s[i-1]) f=true; if(f) cout<<"NO"<<endl; else cout<<"YES"<<endl; } return 0; }