Prefix Sum Addicts

题意翻译

## 题目描述 假设$a_1,a_2,\dots,a_n$是一个长度为$n$的有序整数序列，满足$a_1\leq a_2\leq\dots\leq a_n$ 定义$s_i$为$a_1,a_2,\dots,a_i$的前缀和。 $$ s_i=\sum_{k=1}^{i}a_k=a_1+a_2+\dots+a_i $$ 现在已知前缀和的最后$k$项，即$s_{n−k+1},\dots,s_{n−1},s_n$。你的任务是确定这是否可能。 形式上，给定$k$个整数$s_{n−k+1},\dots,s_{n−1},s_n$，任务是检查是否有一个序列$a_1,a_2,\dots,a_n$，该序列满足以下两个条件: * $a_1 \leq a_2 \dots \leq a_n$ * 对于所有的$n-k+1\leq i\leq n$,满足$s_i=a_1+a_2+\dots+a_i$ ## 输入格式 每个测试包含多个测试用例。第一行包含一个整数$t$($1≤t≤10^5$)——测试用例的数量。下面几行包含了每个测试用例的描述。 每个测试用例的第一行包含两个整数$n$($1≤n≤10^5$)和$k$($1≤k≤n$)，分别表示序列a的长度和前缀和的项数。 每个测试用例的第二行包含$k$个整数$s_{n−k+1}$，…，$s_{n−1}$,$s_n$ (对于每个$n−k+1≤i≤n$，$−10^9≤s_i≤10^9$)。 可以保证所有测试用例的$n$之和不超过$10^5$。 ## 输出格式 可以构造符合条件的$a$序列，输出$\text{Yes}$，否则输出$\text{No}$,换行输出

题目描述

Suppose $ a_1, a_2, \dots, a_n $ is a sorted integer sequence of length $ n $ such that $ a_1 \leq a_2 \leq \dots \leq a_n $ . For every $ 1 \leq i \leq n $ , the prefix sum $ s_i $ of the first $ i $ terms $ a_1, a_2, \dots, a_i $ is defined by $ $ s_i = \sum_{k=1}^i a_k = a_1 + a_2 + \dots + a_i. $ $ </p><p>Now you are given the last $ k $ terms of the prefix sums, which are $ s\_{n-k+1}, \\dots, s\_{n-1}, s\_{n} $ . Your task is to determine whether this is possible. </p><p>Formally, given $ k $ integers $ s\_{n-k+1}, \\dots, s\_{n-1}, s\_{n} $ , the task is to check whether there is a sequence $ a\_1, a\_2, \\dots, a\_n $ such that </p><ol> <li> $ a\_1 \\leq a\_2 \\leq \\dots \\leq a\_n $ , and </li><li> $ s\_i = a\_1 + a\_2 + \\dots + a\_i $ for all $ n-k+1 \\leq i \\leq n$.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains an integer $ t $ ( $ 1 \leq t \leq 10^5 $ ) — the number of test cases. The following lines contain the description of each test case. The first line of each test case contains two integers $ n $ ( $ 1 \leq n \leq 10^5 $ ) and $ k $ ( $ 1 \leq k \leq n $ ), indicating the length of the sequence $ a $ and the number of terms of prefix sums, respectively. The second line of each test case contains $ k $ integers $ s_{n-k+1}, \dots, s_{n-1}, s_{n} $ ( $ -10^9 \leq s_i \leq 10^9 $ for every $ n-k+1 \leq i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case, output "YES" (without quotes) if it is possible and "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

输入输出样例

输入样例 #1

4
5 5
1 2 3 4 5
7 4
-6 -5 -3 0
3 3
2 3 4
3 2
3 4

输出样例 #1

Yes
Yes
No
No

说明

In the first test case, we have the only sequence $ a = [1, 1, 1, 1, 1] $ . In the second test case, we can choose, for example, $ a = [-3, -2, -1, 0, 1, 2, 3] $ . In the third test case, the prefix sums define the only sequence $ a = [2, 1, 1] $ , but it is not sorted. In the fourth test case, it can be shown that there is no sequence with the given prefix sums.

**题目大意：**

假设给定一个长度为 $ n $ 的非降整数序列 $ a_1, a_2, \dots, a_n $，其中 $ a_1 \leq a_2 \leq \dots \leq a_n $。对于序列的每一个位置 $ i $，定义它的前缀和 $ s_i $ 为序列 $ a_1, a_2, \dots, a_i $ 的元素之和，即 $ s_i = \sum_{k=1}^{i}a_k = a_1 + a_2 + \dots + a_i $。

现在已知前缀和的最后 $ k $ 项，即 $ s_{n-k+1}, \dots, s_{n-1}, s_n $。任务是要确定是否存在这样一个序列 $ a_1, a_2, \dots, a_n $，使得它满足以下两个条件：
* $ a_1 \leq a_2 \leq \dots \leq a_n $
* 对于所有的 $ n-k+1 \leq i \leq n $，满足 $ s_i = a_1 + a_2 + \dots + a_i $

**输入格式：**
每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 $ n $（$ 1 \leq n \leq 10^5 $）和 $ k $（$ 1 \leq k \leq n $），分别表示序列 $ a $ 的长度和前缀和的项数。
每个测试用例的第二行包含 $ k $ 个整数 $ s_{n-k+1}, \dots, s_{n-1}, s_n $（对于每个 $ n-k+1 \leq i \leq n $，$ -10^9 \leq s_i \leq 10^9 $）。
可以保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。

**输出格式：**
对于每个测试用例，如果可以构造符合条件的序列 $ a $，输出 "Yes"，否则输出 "No"，每个测试用例结果占一行。**题目大意：** 假设给定一个长度为 $ n $ 的非降整数序列 $ a_1, a_2, \dots, a_n $，其中 $ a_1 \leq a_2 \leq \dots \leq a_n $。对于序列的每一个位置 $ i $，定义它的前缀和 $ s_i $ 为序列 $ a_1, a_2, \dots, a_i $ 的元素之和，即 $ s_i = \sum_{k=1}^{i}a_k = a_1 + a_2 + \dots + a_i $。 现在已知前缀和的最后 $ k $ 项，即 $ s_{n-k+1}, \dots, s_{n-1}, s_n $。任务是要确定是否存在这样一个序列 $ a_1, a_2, \dots, a_n $，使得它满足以下两个条件： * $ a_1 \leq a_2 \leq \dots \leq a_n $ * 对于所有的 $ n-k+1 \leq i \leq n $，满足 $ s_i = a_1 + a_2 + \dots + a_i $ **输入格式：** 每个测试包含多个测试用例。第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^5 $）——测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $（$ 1 \leq n \leq 10^5 $）和 $ k $（$ 1 \leq k \leq n $），分别表示序列 $ a $ 的长度和前缀和的项数。 每个测试用例的第二行包含 $ k $ 个整数 $ s_{n-k+1}, \dots, s_{n-1}, s_n $（对于每个 $ n-k+1 \leq i \leq n $，$ -10^9 \leq s_i \leq 10^9 $）。 可以保证所有测试用例的 $ n $ 之和不超过 $ 10^5 $。 **输出格式：** 对于每个测试用例，如果可以构造符合条件的序列 $ a $，输出 "Yes"，否则输出 "No"，每个测试用例结果占一行。