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

::::info[题目背景已折叠] 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