A painful implementation problem
Разница между en4 и en5, 0 символ(ов) изменены
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). 

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский dvdg6566 2020-11-08 12:30:17 0 (published)
en4 Английский dvdg6566 2020-11-08 12:29:51 13 Tiny change: 'ates, are \textbf{unique}. \n\nOutp' -> 'ates, are **unique**. \n\nOutp'
en3 Английский dvdg6566 2020-11-08 12:28:47 30 Tiny change: ':A_Wallaby,2020-11-08]. Majorit' -> ':A_Wallaby]. Majorit'
en2 Английский dvdg6566 2020-11-08 12:27:48 1145
en1 Английский dvdg6566 2020-11-08 12:19:30 696 Initial revision (saved to drafts)