P2496 [SDOI2012] Physical Education Class

It is time for another PE class. There are $n$ students standing in a row. They all dislike the student at the first position. For any student behind the first one, if they are taller than the first student, they gain a happiness value equal to their height minus the height of the first student. If a student is shorter than the first student, their happiness value is $0$. Now the PE teacher comes with magical powers and can perform the following three operations: 1. Query the maximum happiness value within a given interval. 2. Swap two students. 3. Select an interval and add $t$ to the first person in the interval, $2t$ to the second, $3t$ to the third, and so on. However, the teacher cannot count well, so he asks you to answer each query. For clarity, for an interval $[l, r]$, define the happiness of position $i$ ($l \le i \le r$) as $\max(0, a_i - a_l)$. Operation $1$ asks for the maximum of these values over $i \in [l, r]$.

The first line contains two integers $n, m$, the number of students and the number of operations. The second line contains $n$ integers, the heights $a_i$ of the students in order. Each of the following $m$ lines starts with an integer $type$ indicating the operation: - If $type = 1$, then two integers $l, r$ follow, asking for the maximum happiness value in interval $[l, r]$ as defined above. - If $type = 2$, then two integers $a, b$ follow, indicating to swap the students at positions $a$ and $b$. - If $type = 3$, then three integers $l, r, t$ follow, indicating that for every $i$ with $l \le i \le r$, add $(i - l + 1) \times t$ to $a_i$.

For each query, output the answer to every operation $1$ in order.

Constraints - For $20\%$ of the testdata, $1 \le n, m \le 5 \times 10^3$. - Additionally, in $10\%$ of the testdata, there is no operation $3$. - Additionally, in $20\%$ of the testdata, there is no operation $2$. - For $100\%$ of the testdata, $1 \le n, m \le 10^5$, $0 \le t \le 10^4$, $1 \le a_i \le 10^8$. Translated by ChatGPT 5