Subsequence Addition

# 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;
}