P1253 Fusu's Problem

Given a sequence $a$ of length $n$, support the following three operations: 1. Given a range $[l, r]$, set every number in the range to $x$. 2. Given a range $[l, r]$, add $x$ to every number in the range. 3. Given a range $[l, r]$, query the maximum value in the range.

The first line contains two integers, the length of the sequence $n$ and the number of operations $q$. The second line contains $n$ integers, where the $i$-th integer is the $i$-th number $a_i$ in the sequence. Then follow $q$ lines, each representing an operation. Each line starts with an integer $op$ indicating the type of operation. - If $op = 1$, then there are three integers $l, r, x$, meaning set every number in the range $[l, r]$ to $x$. - If $op = 2$, then there are three integers $l, r, x$, meaning add $x$ to every number in the range $[l, r]$. - If $op = 3$, then there are two integers $l, r$, meaning query the maximum value in the range $[l, r]$.

For each operation with $op = 3$, output one line with a single integer representing the answer.

Constraints - For $10\%$ of the testdata, $n = q = 1$. - For $40\%$ of the testdata, $n, q \leq 10^3$. - For $50\%$ of the testdata, $0 \leq a_i, x \leq 10^4$. - For $60\%$ of the testdata, $op \neq 1$. - For $90\%$ of the testdata, $n, q \leq 10^5$. - For $100\%$ of the testdata, $1 \leq n, q \leq 10^6$, $1 \leq l, r \leq n$, $op \in \{1, 2, 3\}$, $|a_i|, |x| \leq 10^9$. Please note the impact of large input on program efficiency. Translated by ChatGPT 5