Kevin and Nivek
Contest: IAEPC Preliminary Contest (Codeforces Round 999, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: divide and conquer, dp

Kevin and Nivek are competing for the title of "The Best Kevin". They aim to determine the winner through $$$n$$$ matches.

The $$$i$$$-th match can be one of two types:

- Type 1: Kevin needs to spend $$$a_i$$$ time to defeat Nivek and win the match. If Kevin doesn't spend $$$a_i$$$ time on it, Nivek will win the match.
- Type 2: The outcome of this match depends on their historical records. If Kevin's number of wins is greater than or equal to Nivek's up to this match, then Kevin wins. Otherwise, Nivek wins.

Kevin wants to know the minimum amount of time he needs to spend to ensure he wins at least $$$k$$$ matches.

Output the answers for $$$k = 0, 1, \ldots, n$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of matches.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-1 \leq a_i \leq 10^9$$$).

If $$$a_i = -1$$$, the $$$i$$$-th match is of Type 2. Otherwise, the $$$i$$$-th match is of Type 1, and $$$a_i$$$ represents the amount of time Kevin needs to spend to win this match.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, output $$$n + 1$$$ integers. The $$$i$$$-th integer represents the minimum amount of time to win at least $$$i-1$$$ matches.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case, all matches are of Type 2. Kevin can automatically win all matches.

In the second test case, all matches are of Type 1. Kevin can choose matches in increasing order of $$$a_i$$$.

In the third test case:

- If Kevin spends $$$a_1$$$ time on match $$$1$$$, he can win matches $$$1, 2, 3, 4$$$.
- If Kevin spends $$$a_5$$$ time on match $$$5$$$, he can win match $$$5$$$.
- If Kevin spends $$$a_1$$$ time on match $$$1$$$ and $$$a_5$$$ time on match $$$5$$$, he can win all matches.

Example input:
3
5
-1 -1 -1 -1 -1
5
3 2 5 4 1
5
100 -1 -1 -1 1

Example output:
0 0 0 0 0 0 
0 1 3 6 10 15 
0 1 100 100 100 101

Editorial:
First, there is a straightforward dynamic programming solution with a time complexity of $$$O(n^2)$$$.
Let $$$dp(i, j)$$$ represent the minimum cost for Kevin to achieve $$$j$$$ victories in the first $$$i$$$ games. However, optimizing this dynamic programming solution directly is difficult because it lacks convexity.
Therefore, we use a divide-and-conquer approach to solve it (which is more commonly seen in certain counting problems).
—
Key Idea: To compute $$$dp(r, *)$$$ from $$$dp(l, *)$$$ efficiently, the following observations are used:
At time $$$l$$$, if the difference between Kevin's and Nivek's number of victories exceeds $$$r-l$$$, then:
• For Type 2 matches, Kevin will either always win or always lose.
• For Type 1 matches, Kevin should prioritize matches with the smallest cost $$$a_i$$$ in ascending order.
Let $$$g(i)$$$ denote the minimum cost of selecting $$$i$$$ matches in this range, and let $$$t$$$ represent the number of Type 2 matches in the interval.
When $$$j - (l - j) > r-l$$$, the following transition applies: $$$$$$dp(l,j)+g(i) \to dp(r,j+t+i).$$$$$$
Similarly, when $$$j - (l - j) < -(r-l)$$$, a similar transition is used.
Since $$$g(i)$$$ is convex, the best transition point is monotonic. This property allows us to optimize this part using divide-and-conquer, achieving a time complexity of $$$O(n \log n)$$$.
For the case where $$$|j - (l - j)| \leq r-l$$$, brute force is used to compute the transitions explicitly, with a time complexity of $$$O((r-l)^2)$$$.
By dividing the sequence into blocks of size $$$O(\sqrt{n \log n})$$$, the overall time complexity can be reduced to $$$O(n \sqrt{n \log n})$$$.
—
To further optimize the problem, a more refined strategy is applied. Specifically, for the case where $$$|j - (l - j)| \leq r-l$$$, instead of computing transitions explicitly with brute force, we recursively divide the problem into smaller subproblems. The goal in each subproblem is to compute the transitions from a segment of $$$dp(l)$$$ to $$$dp(r)$$$, ensuring that the segment length in $$$dp(l)$$$ does not exceed $$$O(r-l)$$$.
Let $$$m = \lfloor\frac{l + r}{2}\rfloor$$$. First, compute the transitions from $$$dp(l)$$$ to $$$dp(m)$$$. Then, use the results from $$$dp(m)$$$ to compute the transitions from $$$dp(m)$$$ to $$$dp(r)$$$. For each subinterval, the strategy remains the same:
• For differences in the number of victories that exceed the interval length, apply monotonicity to handle the transitions efficiently.
• For the remaining part, recursively compute transitions using the same divide-and-conquer approach.
The recurrence relation for this approach is: $$$T(n)=2T(n/2) + O(n \log n)$$$ So the time complexity is $$$T(n)=O(n \log^2 n)$$$.