P5611 [Ynoi2013] D2T2

Given a sequence of length $n$, there are $m$ query operations. Each query is in the form $l\;r\;L\;R$. It means: keep the positions whose values are in $[L,R]$ unchanged, and set all other positions to $0$. Then, compute the maximum subarray sum within the interval $[l,r]$ of the resulting sequence. This subarray is allowed to be empty.

The first line contains two integers $n,m$. The second line contains $n$ integers representing the sequence. Then follow $m$ lines, each containing four integers $l\;r\;L\;R$, representing one query operation.

Output $m$ lines, each containing one integer representing the answer.

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477. Constraints: for $100\%$ of the testdata, $1\leq n,m \le 10^5$, and the absolute value of every number in the sequence is $\le 10^9$. In the fourth group of queries, the value range limit is $[-1,5]$, and the sequence becomes `-1 1 0 5 -1 4`. The maximum subarray in interval $[1,6]$ is $[2,6]$, with sum $9$. In the fifth group of queries, the value range limit is $[2,5]$, and the sequence becomes `0 0 0 5 0 4`. The maximum subarray in interval $[2,5]$ is $[4,4]$ (tied), with sum $5$. Translated by ChatGPT 5