Fill the Matrix
Contest: Educational Codeforces Round 150 (Rated for Div. 2)
Difficulty rating: 2200
Tags: data structures, greedy, math

There is a square matrix, consisting of $$$n$$$ rows and $$$n$$$ columns of cells, both numbered from $$$1$$$ to $$$n$$$. The cells are colored white or black. Cells from $$$1$$$ to $$$a_i$$$ are black, and cells from $$$a_i+1$$$ to $$$n$$$ are white, in the $$$i$$$-th column.

You want to place $$$m$$$ integers in the matrix, from $$$1$$$ to $$$m$$$. There are two rules:

- each cell should contain at most one integer;
- black cells should not contain integers.

The beauty of the matrix is the number of such $$$j$$$ that $$$j+1$$$ is written in the same row, in the next column as $$$j$$$ (in the neighbouring cell to the right).

What's the maximum possible beauty of the matrix?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the matrix.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$) — the number of black cells in each column.

The third line contains a single integer $$$m$$$ ($$$0 \le m \le \sum \limits_{i=1}^n n - a_i$$$) — the number of integers you have to write in the matrix. Note that this number might not fit into a 32-bit integer data type.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the maximum beauty of the matrix after you write all $$$m$$$ integers in it. Note that there are no more integers than the white cells, so the answer always exists.

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

Example input:
6
3
0 0 0
9
4
2 0 3 1
5
4
2 0 3 1
6
4
2 0 3 1
10
10
0 2 2 1 5 10 3 4 1 1
20
1
1
0

Example output:
6
3
4
4
16
0

Editorial:
Notice that the rows of the matrix are basically independent. When we fill the matrix with integers, the values from the rows are just added together. Moreover, in a single row, the segments of white cells separated by black cells are also independent in the same way.
And how to solve the problem for one segment of white cells? Obviously, put the numbers one after another. Placing a non-zero amount of integers $$$k$$$ will yield the result of $$$k-1$$$. Thus, the answer is $$$\sum_\limits{i=1}^s k_i - 1$$$, where $$$s$$$ is the number of used segments. We know that the sum of $$$k_i$$$ is just $$$m$$$. So it becomes $$$m + \sum_\limits{i=1}^s -1 = m - s$$$. So, the problem asks us to minimize the number of used segments.
In order to use the smallest number of segments, we should pick the longest ones. We only have to find them.
In the worst case, there are $$$O(n^2)$$$ segments of white cells in the matrix. However, we can store them in a compressed form. Since their lengths are from $$$1$$$ to $$$n$$$, we can calculate how many segments of each length there are.
Look at the matrix from the bottom to the top. First, there are some fully white rows. Then some black cell appears and splits the segment of length $$$n$$$ into two segments. Maybe more if there are more black cells in that row. After that the split segments behave independently of each other.
Let's record these intervals of rows each segment exists at. So, let some segment exist from row $$$l$$$ to row $$$r$$$. What does that mean? This segment appeared because of some split at row $$$r$$$. At row $$$l$$$, some black cell appeared that split the segment in parts. If we knew the $$$r$$$ for the segment, we could've saved the information about it during the event at row $$$l$$$.
So, we need a data structure that can support the following operations:
• find a segment that covers cell $$$x$$$;
• erase a segment;
• insert a segment.
Additionally, that data structure should store a value associated with a segment. Thus, let's use a map. For a segment, which is a pair of integers, store another integer — the bottommost row this segment exists.
Make events $$$(a_i, i)$$$ for each column $$$i$$$. Sort them and process in a non-increasing order. During the processing of the event, find the segment this black cell splits. Save the information about this segment. Then remove it and add two new segments (or less if some are empty): the one to the left and the one to the right.
At the end, for each length from $$$1$$$ to $$$n$$$, we will have the number of segments of such length. In order to fill them with $$$m$$$ integers, start with the longest segments and use as many of each length as possible. So, while having $$$m$$$ more integers to place and $$$\mathit{cnt}$$$ segments of length $$$\mathit{len}$$$, you can use $$$\min(\lfloor \frac{m}{\mathit{len}} \rfloor, cnt)$$$ of segments.
Overall complexity: $$$O(n \log n)$$$ per testcase.