WARNING: DISGUSTING PROBLEM ALERT
At the start of the year, I wrote a very painful implementation problem. My official solution was over 200 lines long and I was wondering if anyone could come up with a more elegant solution.
The problem is as follows:
The S value of an array is the sum of maximum values across all continuous subsequences length at least one. In the array $$$(4,5,1)$$$, the value is $$$4+5+1+5+5+5=25$$$.
You are given an array $$$A$$$ of length $$$N$$$. There are $$$N$$$ updates, where the $$$I$$$th update increases the $$$i$$$th value of the array by a value $$$B_i$$$. It is guaranteed that all $$$2N$$$ values, before and after updates, are unique.
Output $$$N+1$$$ integers, the initial S value and the S value after every update.
$$$N \leq 5 \cdot 10^5$$$
Given some subtasks, the highest score was 72 by A_Wallaby. Majority of participants scored 27 points, where $$$B_i = 0$$$ for all $$$i$$$.
Clearly, finding the original solution can be done using either divide and conquer or monotonic stack.
Consider the contribution given by a value the number of subarrays in which that number is the greatest value. The right side of the contribution can be maintained with a range max binary search segment tree. The left side can be found using a descretised lazy update segment tree.
This problem is by no measure an elegant problem. It took me close to 4h to implement. I was wondering if anyone could find a more elegant solution? If anyone is interested, here is the problem statement and the solution code.