P6242 [Template] Segment Tree 3 (Range Maximum Operations, Range Historical Maximum)

This problem is a template for using a segment tree to maintain range maximum-related operations and the range historical maximum.

Given a sequence $A$ of length $n$, we also define an auxiliary array $B$. Initially, $B$ is exactly the same as $A$. Then $m$ operations are performed. There are five types of operations, given in the following format: - `1 l r k`: For all $i\in[l,r]$, add $k$ to $A_i$ ($k$ can be negative). - `2 l r v`: For all $i\in[l,r]$, set $A_i$ to $\min(A_i,v)$. - `3 l r`: Compute $\sum_{i=l}^{r} A_i$. - `4 l r`: For all $i\in[l,r]$, compute the maximum value of $A_i$. - `5 l r`: For all $i\in[l,r]$, compute the maximum value of $B_i$. After each operation, we perform an update: $B_i\gets\max(B_i,A_i)$.

The first line contains two positive integers $n,m$, representing the length of sequence $A$ and the number of operations. The second line contains $n$ integers $A_1,A_2,\cdots,A_n$, representing the sequence $A$. The next $m$ lines each start with an integer $op$, representing the operation type. It is followed by two or three integers as the operation parameters. The format is described in the Description section.

For operations with $op\in\{3,4,5\}$, output one line containing one integer, which is the answer to the query.

#### Sample Explanation \#1 #### | Operation Count | Input | Operation | Sequence | Output | | :----------: | :----------: | :----------: | :----------: | :----------: | | 0 | | | $1,2,3,4,5$ | | | 1 | `3 2 5` | Find the sum of all numbers in $[2,5]$ | $1,2,3,4,5$ | `14` | | 2 | `1 1 3 3` | Add $3$ to all numbers in $[1,3]$ | $4,5,6,4,5$ | | | 3 | `4 2 4` | Find the maximum of all numbers in $[2,4]$ | $4,5,6,4,5$ | `6` | | 4 | `2 3 4 1` | Replace all numbers in $[3,4]$ with the minimum of itself and $1$ | $4,5,1,1,5$ | | | 5 | `5 1 5` | Find the maximum among the historical maximum values over $[1,5]$ | $4,5,1,1,5$ | `6` | | 6 | `3 1 4` | Find the sum of all numbers in $[1,4]$ | $4,5,1,1,5$ | `11` | #### Constraints - For test points $1,2$, $n,m\leq 5000$. - For test points $3,4$, $op\in\{1,2,3,4\}$. - For test points $5,6$, $op\in\{1,3,4,5\}$. - For all testdata, it is guaranteed that $1\leq n,m\leq 5\times 10^5$, $-5\times10^8\leq A_i\leq 5\times10^8$, $op\in[1,5]$, $1 \leq l\leq r \leq n$, $-2000\leq k\leq 2000$, and $-5\times10^8\leq v\leq 5\times10^8$. #### Note #### The input size of this problem is large. Please use a reasonable and efficient input method. Translated by ChatGPT 5