P8024 [ONTAK2015] Stumilowy sad

Subtask 0 uses the original testdata, and Subtask 1 uses hack testdata.

On a straight road from left to right, there are $n$ regions. Each region initially has a tree planted in it. The tree in region $i$ has height $h_i$. You need to process $q$ operations: - `1 l r c`: Increase the heights of all trees in regions $l$ to $r$ by $c$ units. - `2 l r h`: Fix a knife in the air at height $h$ and cut all trees in regions $l$ to $r$. - `3 l r h`: Plant a new tree of height $h$ in each region from $l$ to $r$. - `4 l r`: Query the height of the tallest tree in regions $l$ to $r$. Note: In this problem, height is measured relative to some horizontal plane, so **negative values may appear**.

The first line contains two integers $n, q$. The second line contains $n$ integers $h_1, h_2, \cdots, h_n$. The next $q$ lines each contain three or four integers: $op, l, r, c$, $op, l, r, h$, or $op, l, r$.

Output several lines, each containing one integer, which is the answer to the corresponding query.

For $100\%$ of the data, $1 \leq n, q \leq 5 \times 10^5$, $1 \leq h_i \leq 10^9$, $1 \leq l \leq r \leq n$, $0 \leq |c| \leq 500$, $1 \leq h \leq 10^9$. Translated by ChatGPT 5