Least Prefix Sum

题意翻译

定义长度为 $n$ 的数组 $arr$ 的前缀和数组为 $s$，对于一次操作，你可以选择一个数，变为这个数的相反数，给定一个数 $m$，请你求出最小的操作次数使序列满足：$\forall i\in[1,n], s_i\geq s_m$。

题目描述

Baltic, a famous chess player who is also a mathematician, has an array $ a_1,a_2, \ldots, a_n $ , and he can perform the following operation several (possibly $ 0 $ ) times: - Choose some index $ i $ ( $ 1 \leq i \leq n $ ); - multiply $ a_i $ with $ -1 $ , that is, set $ a_i := -a_i $ . Baltic's favorite number is $ m $ , and he wants $ a_1 + a_2 + \cdots + a_m $ to be the smallest of all non-empty prefix sums. More formally, for each $ k = 1,2,\ldots, n $ it should hold that $ $a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m. $ $ </p><p>Please note that multiple smallest prefix sums may exist and that it is only required that $ a\_1 + a\_2 + \\cdots + a\_m $ is one of them.</p><p>Help Baltic find the minimum number of operations required to make $ a\_1 + a\_2 + \\cdots + a\_m$ the least of all prefix sums. It can be shown that a valid sequence of operations always exists.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 10\,000 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \leq m \leq n \leq 2\cdot 10^5 $ ) — the size of Baltic's array and his favorite number. The second line contains $ n $ integers $ a_1,a_2, \ldots, a_n $ ( $ -10^9 \leq a_i \leq 10^9 $ ) — the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print a single integer — the minimum number of required operations.

输入输出样例

输入样例 #1

6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873

输出样例 #1

1
1
0
0
3
4

说明

In the first example, we perform the operation $ a_4 := -a_4 $ . The array becomes $ [-1,-2,-3,4] $ and the prefix sums, $ [a_1, \ a_1+a_2, \ a_1+a_2+a_3, \ a_1+a_2+a_3+a_4] $ , are equal to $ [-1,-3,-6,-2] $ . Thus $ a_1 + a_2 + a_3=-6 $ is the smallest of all prefix sums. In the second example, we perform the operation $ a_3 := -a_3 $ . The array becomes $ [1,2,-3,4] $ with prefix sums equal to $ [1,3,0,4] $ . In the third and fourth examples, $ a_1 + a_2 + \cdots + a_m $ is already the smallest of the prefix sums — no operation needs to be performed. In the fifth example, a valid sequence of operations is: - $ a_3 := -a_3 $ , - $ a_2 := -a_2 $ , - $ a_5 := -a_5 $ . The array becomes $ [-2,-3,5,-5,20] $ and its prefix sums are $ [-2,-5,0,-5,15] $ . Note that $ a_1+a_2=-5 $ and $ a_1+a_2+a_3+a_4=-5 $ are both the smallest of the prefix sums (and this is a valid solution).

**最小前缀和**

**题意翻译**
定义一个长度为 $ n $ 的数组 $ arr $ 的前缀和数组为 $ s $，你可以选择一个数，变为这个数的相反数，给定一个数 $ m $，求出最小的操作次数使序列满足：对于所有 $ i $ 属于 $[1,n]$，$ s_i \geq s_m $。

**题目描述**
著名的国际象棋选手兼数学家Baltic有一个数组 $ a_1, a_2, \ldots, a_n $，他可以进行以下操作若干次（可能为0次）：

- 选择一个索引 $ i $（$ 1 \leq i \leq n $）；
- 将 $ a_i $ 乘以 $ -1 $，即，设置 $ a_i := -a_i $。

Baltic最喜欢的数字是 $ m $，他希望 $ a_1 + a_2 + \cdots + a_m $ 是所有非空前缀和中最小的。更正式地说，对于每个 $ k = 1,2,\ldots, n $，都应该满足 $ a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m $。请注意，可能存在多个最小的前缀和，但只需要 $ a_1 + a_2 + \cdots + a_m $ 是其中之一。

帮助Baltic找到使 $ a_1 + a_2 + \cdots + a_m $ 成为所有前缀和中最小所需的最小操作次数。可以证明，总是存在一个有效的操作序列。

**输入输出格式**

**输入格式**
每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \leq t \leq 10,000 $）。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \leq m \leq n \leq 2 \times 10^5 $）——Baltic的数组大小和他最喜欢的数字。

第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \leq a_i \leq 10^9 $）——数组。

保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。

**输出格式**
对于每个测试用例，打印一个整数——所需的最小操作次数。

**输入输出样例**

**输入样例 #1**
```
6
4 3
-1 -2 -3 -4
4 3
1 2 3 4
1 1
1
5 5
-2 3 -5 1 -20
5 2
-2 3 -5 -5 -20
10 4
345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873
```

**输出样例 #1**
```
1
1
0
0
3
4
```

**说明**
在第一个例子中，我们执行操作 $ a_4 := -a_4 $。数组变为 $ [-1,-2,-3,4] $，前缀和 $ [a_1, a_1+a_2, a_1+a_2+a_3, a_1+a_2+a_3+a_4] $ 分别为 $ [-1,-3,-6,-2] $。因此 $ a_1 + a_2 + a_3=-6 $ 是所有前缀和中最小的。

在第二个例子中，我们执行操作 $ a_3 := -a_3 $。数组变为 $ [1,2,-3,4] $，前缀和为 $ [1,3,0,4] $。

在第三个和第四个例子中，$ a_1 + a_2 + \cdots + a_m $ 已经是前缀和中最小的——不需要执行任何操作。

在第五个例子中，一个有效的操作序列是：

- $ a_3 := -a_3 $，
- $ a_2 := -a_2 $，
- $ a_5 := -a_5 $。

数组变为 $ [-2,-3,5,-5,20] $，其前缀和为 $ [-2,-5,0,-5,15] $。注意 $ a_1+a_2=-5 $ 和 $ a_1+a_2+a_3+a_4=-5 $ 都是前缀和中最小的（这是一个**最小前缀和** **题意翻译** 定义一个长度为 $ n $ 的数组 $ arr $ 的前缀和数组为 $ s $，你可以选择一个数，变为这个数的相反数，给定一个数 $ m $，求出最小的操作次数使序列满足：对于所有 $ i $ 属于 $[1,n]$，$ s_i \geq s_m $。 **题目描述** 著名的国际象棋选手兼数学家Baltic有一个数组 $ a_1, a_2, \ldots, a_n $，他可以进行以下操作若干次（可能为0次）： - 选择一个索引 $ i $（$ 1 \leq i \leq n $）； - 将 $ a_i $ 乘以 $ -1 $，即，设置 $ a_i := -a_i $。 Baltic最喜欢的数字是 $ m $，他希望 $ a_1 + a_2 + \cdots + a_m $ 是所有非空前缀和中最小的。更正式地说，对于每个 $ k = 1,2,\ldots, n $，都应该满足 $ a_1 + a_2 + \cdots + a_k \geq a_1 + a_2 + \cdots + a_m $。请注意，可能存在多个最小的前缀和，但只需要 $ a_1 + a_2 + \cdots + a_m $ 是其中之一。 帮助Baltic找到使 $ a_1 + a_2 + \cdots + a_m $ 成为所有前缀和中最小所需的最小操作次数。可以证明，总是存在一个有效的操作序列。 **输入输出格式** **输入格式** 每个测试包含多个测试用例。第一行包含测试用例的数量 $ t $（$ 1 \leq t \leq 10,000 $）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \leq m \leq n \leq 2 \times 10^5 $）——Baltic的数组大小和他最喜欢的数字。 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ -10^9 \leq a_i \leq 10^9 $）——数组。 保证所有测试用例的 $ n $ 之和不超过 $ 2 \times 10^5 $。 **输出格式** 对于每个测试用例，打印一个整数——所需的最小操作次数。 **输入输出样例** **输入样例 #1** ``` 6 4 3 -1 -2 -3 -4 4 3 1 2 3 4 1 1 1 5 5 -2 3 -5 1 -20 5 2 -2 3 -5 -5 -20 10 4 345875723 -48 384678321 -375635768 -35867853 -35863586 -358683842 -81725678 38576 -357865873 ``` **输出样例 #1** ``` 1 1 0 0 3 4 ``` **说明** 在第一个例子中，我们执行操作 $ a_4 := -a_4 $。数组变为 $ [-1,-2,-3,4] $，前缀和 $ [a_1, a_1+a_2, a_1+a_2+a_3, a_1+a_2+a_3+a_4] $ 分别为 $ [-1,-3,-6,-2] $。因此 $ a_1 + a_2 + a_3=-6 $ 是所有前缀和中最小的。 在第二个例子中，我们执行操作 $ a_3 := -a_3 $。数组变为 $ [1,2,-3,4] $，前缀和为 $ [1,3,0,4] $。 在第三个和第四个例子中，$ a_1 + a_2 + \cdots + a_m $ 已经是前缀和中最小的——不需要执行任何操作。 在第五个例子中，一个有效的操作序列是： - $ a_3 := -a_3 $， - $ a_2 := -a_2 $， - $ a_5 := -a_5 $。 数组变为 $ [-2,-3,5,-5,20] $，其前缀和为 $ [-2,-5,0,-5,15] $。注意 $ a_1+a_2=-5 $ 和 $ a_1+a_2+a_3+a_4=-5 $ 都是前缀和中最小的（这是一个