P5073 [Ynoi Easy Round 2015] The Happiest Girl in the World.

I have a request. The final request. I feel like I once made a promise with him. We agreed that person would not have to fight anymore in the future. We agreed that I would inherit all of that person’s battles. And I still have something I want to say to him, so please.  【No matter what, you must?】 Yes, no matter what. 【But if you do it again, Ctholly will disappear completely.】 【Not only the memories, but also all those precious feelings.】 【All of them will disappear completely!?】 That would be pretty unbearable. But compared to disappearing, I hate even more that it ends like this. 【Ctholly...】 So, please. Let me return to that place once again.  “Ctholly, you can do it.”    Willem... Thank you...

At the very end, Ctholly gives you a sequence of length $n$, with $m$ operations: 1. Global add (i.e., add to all numbers in the sequence). 2. Query the maximum subarray sum in an interval.

The first line contains two integers $n,m$. The second line contains $n$ numbers representing the sequence. Then follow $m$ lines, each describing one operation. * $1\ x$ : Add $x$ to all numbers. * $2\ l\ r$ : Query the maximum subarray sum in the interval $[l,r]$ (you may choose no elements; in this case the maximum subarray sum is $0$).

For each query, output one number as the answer.

Idea: nzhtl1477, Solution: ccz181078, Code: nzhtl1477&w33z8kqrqk8zzzx33, Data: nzhtl1477. Constraints: $1\leq n \leq 3\times 10^5$, $1 \leq m \leq 6\times 10^5$, the absolute value of numbers in the sequence $\leq 2\times 10^9$, and the absolute value of $x$ in operation $1$ is $\leq 5\times 10^7$. Translated by ChatGPT 5