Least Prefix Sum
Contest: Hello 2023
Difficulty rating: 1600
Tags: data structures, greedy

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.$$$$$$

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.

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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).

Example input:
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

Example output:
1
1
0
0
3
4

Editorial:
Try a greedy approach.
What data structure supports inserting an element, finding the maximum and erasing the maximum? That is right, a binary heap, or STL priority_queue.
Let pi=a1+a2+…ai and suppose that px<pm for some x<m. Let x be the greatest such integer. Performing an operation to any element in the segment [1,x] does nothing since pm−px stays the same. Similarly, performing an operation to any element in segment [m+1,n] does not affect it.
A greedy idea is to choose the maximal element in segment [x+1,m] and perform an operation on it, because it decreases pm as much as possible. Repeat this process until pm eventually becomes less than or equal to px. It might happen that a new py such that py<pm and y<x emerges. In that case, simply repeat the algorithm until pm is less than or equal to any prefix sum in its "left".
Suppose that px<pm and x>m now. The idea is the same, choose a minimal element in segment [m+1,x] and perform an operation on it as it increases px as much as possible. And repeat the algorithm as long as such x exists.
To implement this, solve the two cases independently. Let's describe the first case as the second one is analogous. Iterate over i from m to 1 and maintain a priority queue. If pi<pm, pop the queue (possibly multiple times) and decrease pm accordingly (we simulate performing the "optimal" operations). Notice that one does not have to update any element other than pm. Add ai to the priority queue afterwards.
The time complexity is O(nlogn).