P6792 [SNOI2020] Interval Sum

There is an integer sequence $a_1,a_2,\cdots,a_n$ of length $n$ (it may contain negative numbers). Now perform $q$ operations on it. Each operation is one of the following: - `0 l r x` means for $[l,r]$, assign $a_i$ to $\max(a_i,x)$; - `1 l r` asks for the maximum subarray sum in the interval $[l,r]$, i.e. $\max(0, \max_{l\le u\le v\le r} (\sum_{i=u}^v a_i))$.

The first line contains two positive integers $n,q$, representing the sequence length and the number of operations. The second line contains $n$ positive integers $a_1,a_2,\cdots,a_n$, representing the initial sequence. The next $q$ lines each are in the form `0 l r x` or `1 l r`, representing one operation.

For each operation of the form `1 l r`, output one integer per line, representing the answer.

#### Sample Explanation For sample $1$: - At the 1st query, the sequence is $2,-4,6,-5,5$, and the maximum subarray sum is $6$. - At the 2nd query, the sequence is $2,-4,6,-4,5$, and the maximum subarray sum is $7$. - At the 3rd query, the sequence is $2,-4,6,-1,5$, and the maximum subarray sum is $10$. - At the 4th query, the sequence is $2,-1,6,-1,5$, and the maximum subarray sum is $11$. #### Constraints For all testdata, $1\le n\le 10^5$, $1\le q\le 2\times 10^5$, $|a_i|, |x|\le 10^9$. - For $10\%$ of the testdata, $n,q \le 200$. - For another $10\%$ of the testdata, $n,q \le 2000$. - For another $25\%$ of the testdata, each operation $0$ satisfies $l=r$ (i.e. only point updates). - For another $20\%$ of the testdata, each operation $1$ satisfies $l=1,r=n$ (i.e. only global queries). - For the remaining $35\%$ of the testdata, there are no special constraints. **There are 3 hack testdata points from the problem setter.** Translated by ChatGPT 5