P4118 [Ynoi2018] What Are You Doing at the End of the World? Are You Busy? Will You Save Us?

Thank you so much for today. You let me experience so many wonderful things. I have left behind memories like a beautiful dream, but time is up. One last favor. I hope you can forget me.  Before I disappear, I hold a wish not to disappear. I hope someone will remember me. I hope to leave a bond. If I wish for that, is there anything wrong?  Sweet and fragrant, it smells so nice. It looks delicious.  I kept... our... our promise. I really... really tried hard...  Welcome back, Chtholly.

Chtholly gives you a sequence $a$ of length $n$, and there are $m$ operations. 1. Add $x$ to all numbers in the interval $[l, r]$. 2. Query the maximum subarray sum in the interval $[l, r]$, where choosing no elements is allowed.

The first line contains two integers $n, m$. The second line contains $n$ integers representing the sequence $a$. The following $m$ lines: - `1 l r x`: add $x$ to all numbers in the interval $[l, r]$. - `2 l r`: query the maximum subarray sum in the interval $[l, r]$, with the empty subarray allowed.

For each query, output one number representing the answer.

Idea: nzhtl1477, Solution: ccz181078, Code: nzhtl1477 & ccz181078 & mrsrz, Data: nzhtl1477 & mrsrz & w33z8kqrqk8zzzx33. $1 \le n , m \le 10^5$, $| a_i | \leq 10^9$, $|x|\leq 10^9$. **It is guaranteed that at any time $|a_i|\leq 2\times 10^9$.** By nzhtl1477 & ccz181078. Translated by ChatGPT 5