P17826 [COCI 2026/2027 #1] Voda

In his yard, Marko has built a **histogram** out of wooden columns: $n$ columns of width $1$ stand next to each other, and the column at position $i$ has height $h_i$. Marko likes to change his work, so sometimes he raises, lowers or replaces some of the columns. Sometimes Marko looks only at **a part of the histogram**, the columns at positions from $l$ to $r$, and imagines a lot of rain falling on them. The columns outside the observed part **do not exist** at that moment, so water can flow away over the left edge of column $l$ and over the right edge of column $r$. The rain falls until the histogram is full: water stays wherever it is trapped by higher columns on both sides, and all other water flows away. One $1\times 1$ cell filled with water is **one unit of water**. We say that a column is **completely under water** if there is water above its top. A column is **not completely under water** if its top is dry, that is, there is no water above it. Water may still touch such a column from the side, up to the height of its top. Marko will make $q$ events in order, and each of them is of one of the following five types: - `1 i x` - the height of column $i$ becomes $x$, - `2 l r x` - the heights of all columns from $l$ to $r$ become $x$, - `3 l r x` - the heights of all columns from $l$ to $r$ increase by $x$ (the number $x$ may also be negative), - `4 l r` - Marko observes the columns from $l$ to $r$ and wants to know how many of them are **not completely under water**, - `5 l r` - Marko observes the columns from $l$ to $r$ and wants to know how many **units of water in total** are held. Help Marko and answer all of his questions. Observing does not change the histogram, and the water disappears after each question.

The first line contains positive integers $n$ and $q$ ($1\le n,q\le 200\,000$), the number of columns and the number of events. The second line contains $n$ integers $h_1,h_2,\ldots,h_n$ ($0\le h_i\le 10^9$), the initial heights of the columns. Each of the following $q$ lines contains the description of one event in one of the forms given above. It holds that $1\le i\le n$ and $1\le l\le r\le n$. In events of types $1$ and $2$, $0\le x\le 10^9$, and in events of type $3$, $-10^9\le x\le 10^9$. It is guaranteed that the heights of all columns are integers between $0$ and $10^9$ at all times.

For each event of type $4$ or $5$, in the order they are given, output the answer to Marko's question in a separate line.

#### Clarification of the first example The histogram is $[3,0,2,4,1,4,0,2]$. In the first question, Marko observes the whole histogram. Water is held above columns $2$, $3$, $5$ and $7$ ($3$, $1$, $3$ and $2$ units, respectively), while the tops of columns $1$, $4$, $6$ and $8$ are dry. These four columns are not completely under water, so the answer is $4$. In the second question, Marko observes the columns $[0,2,4,1]$. The heights first increase and then decrease, so all the water flows away over the left or the right edge. No column is completely under water, and the answer is $4$. #### Clarification of the second example The histogram is $[5,1,3,2,4,1]$. When Marko observes the whole histogram, the water between columns $1$ and $5$ stands up to height $4$, and to the right of column $5$ it all flows away. So $0,3,1,2,0,0$ units of water are held above the columns, $6$ in total. Columns $2$, $3$ and $4$ are completely under water and the remaining three are not, so the answer to the second question is $3$. #### Scoring | Subtask | Points | Constraints | | --- | --- | --- | | 1 | 21 | $n,q\le 5000$. | | 2 | 16 | There are only events of type $4$. | | 3 | 11 | There are only events of types $4$ and $5$. | | 4 | 13 | There are only events of types $1$ and $4$. | | 5 | 14 | There are only events of types $1$, $4$ and $5$. | | 6 | 16 | There are only events of types $1$, $2$, $3$ and $4$. | | 7 | 19 | No additional constraints. |