Background

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

Problem Description

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)$.

Input Format

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.

Output Format

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

5 6
1 2 3 4 5
3 2 5
1 1 3 3
4 2 4
2 3 4 1
5 1 5
3 1 4

14
6
6
11

Hint

Sample Explanation #1

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