P9993 [Ynoi Easy Round 2024] TEST_133

**Please do not abuse the judging system of this problem. If you abuse it, your account will be banned.**

Given a sequence $a_1, \dots, a_n$, there are $m$ operations: - Modify operation: given $l, r, x$, increase the values of $a_l, a_{l+1}, \dots, a_r$ by $x$. - Query operation: given $l, r, x$, ask for the maximum, among all indices $i$ satisfying $l \le i \le r$ and $a_i < x$, of the historical maximum value of $a_i$ (i.e., the maximum among its initial value and its values after each modify operation).

The first line contains two integers $n, m$. The next line contains $n$ integers $a_1, a_2, \dots, a_n$. The next $m$ lines each contain four integers $o, l, r, x$, where $o = 1$ denotes a modify operation, and $o = 2$ denotes a query operation.

For each query operation, output one line with the answer (in particular, if there is no index $i$ that satisfies the condition, output `-inf`).

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078. For $0\%$ of the testdata, $n, m \le 5000$. For another $1/3\%$ of the testdata, the query operations guarantee $l = 1$ and $r = n$. For another $1/3$ of the testdata, there are no modify operations. For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $|a_i| \le 10^9$ (only the initially given sequence guarantees this limit), $1 \le l \le r \le n$, and $|x| \le 10^9$. Translated by ChatGPT 5