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:↵
↵
<spoiler summary="Problem">↵
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$↵
</spoiler>↵
↵
Given some subtasks, the highest score was 72 by [user:A_Wallaby,2020-11-08]. Majority of participants scored 27 points, where $B_i = 0$ for all $i$.↵
↵
<spoiler summary="Solution">↵
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. ↵
</spoiler>↵
↵
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](https://dunjudge.me/analysis/problems/2048/q4_final.pdf) and the [solution code](https://pastebin.com/0SquKUJF).
↵
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:↵
↵
<spoiler summary="Problem">↵
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$↵
</spoiler>↵
↵
Given some subtasks, the highest score was 72 by [user:A_Wallaby,2020-11-08]. Majority of participants scored 27 points, where $B_i = 0$ for all $i$.↵
↵
<spoiler summary="Solution">↵
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. ↵
</spoiler>↵
↵
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](https://dunjudge.me/analysis/problems/2048/q4_final.pdf) and the [solution code](https://pastebin.com/0SquKUJF).
