Link to contest (statement in Vietnamese): https://lqdoj.edu.vn/contest/dhbb23, problem link: https://lqdoj.edu.vn/problem/dhbb23hkdata. (you must virtual join the contest before open the problem)
Summary: Given a array $$$a$$$ with $$$n$$$ elements, the cost of this array is the maximum value of $$$|\sum^{R}_{i = L}\ a_i|$$$ among all pairs $$$1\leq L\leq R\leq n$$$. There are $$$q$$$ $$$\bf {independent}$$$ updates of the form $$$l\ r\ c$$$: increase all elements from $$$l$$$ to $$$r$$$ by $$$c$$$, then calculate the cost of array after the update. $$$n,\ q\leq 10^5,\ |a_i|,\ |c|\leq 10^9$$$.
Thanks for your help and attention, have a good day.
Update: I just solved this problem using a CHT Segment Tree (code here: https://ideone.com/5BWLxX), thanks for all the help!
If the absolute value sign is eliminated, it should be a simple segment tree problem.
To eliminated the absolute value sign, we could see that
Now the problem could be easily solved by a segment tree.
Edit: fixed some grammatical mistakes
I know this, but how do we perform a lazy update for a max/min range segment tree? Or did you mean using another method?
Oh I'm sorry, I haven't think about that.
but I feel like, there must be some way, maybe sqrt decomposition?
I don't know, but I think data structure solutions alone aren't enough for this problem. I tried solving it that way, but I couldn't =)).
Here is similar problem: 52C - Circular RMQ
Also, when looking at the prefix sum, it looked like some extended version of segment tree that I have seen somewhere =))))
By looking at prefix sums this is just the difference between maximum and minimum, and the updates add linear functions (also by bijection of prefix sums, this problem is equivalent)
https://judge.yosupo.jp/problem/range_linear_add_range_min
The general idea I know of is to maintain the dynamic upper convex hull $$$(i, A_i)$$$ with a segment tree. This gives in particular the maximum value, and the updates are friendly to it, but the idea is nontrivial. You can read about it here:
https://mirror.codeforces.com/blog/entry/75929
Auto comment: topic has been updated by nhphuc (previous revision, new revision, compare).