3420. Count Non-Decreasing Subarrays After K Operations

The problem asks to count the number of non-decreasing subarrays that can be formed from a given array after applying up to k increment operations on each subarray. A non-decreasing subarray is one where each element is greater than or equal to its predecessor.

For each possible subarray, we can calculate the minimum number of operations required to make it non-decreasing. This minimum cost is determined by finding the maximum value within each prefix of the subarray and incrementing all elements smaller than this maximum to match it.

The solution employs a monotonic deque to efficiently maintain the block starts of the prefix maximum values as we slide a window across the array. Block starts are positions with the same running maximum, allowing us to group contiguous segments of the array that share the same maximum value.

When expanding the window to the left, we absorb entire blocks whose maximum is less than or equal to the current element (nums[left]). This absorption contributes to the total cost based on the size of each absorbed block.

If the cost exceeds the allowed k operations, we shrink the window from the right by removing elements and adjusting the cost accordingly, which involves subtracting the difference between the prefix maximum at the head of the deque and the element being removed.

For each valid window [left, right], all subarrays within it are counted as they can be made non-decreasing within the k operations. The final answer is the total count of such subarrays across all possible positions in the original array.