P16702 [MCO 2026] Rainwater Collection

In the town of MCO, there are $N$ towers standing side by side. From left to right, the initial height of the $i$-th tower (indexed from $0$) is $H_i$. After a heavy rain, water may accumulate on top of the towers. Evirir, a resident of MCO, wants to know how much rainwater these towers can collect in total. For an interval of towers $[l, r]$ (i.e., towers $l, l+1, \ldots, r$), its rainfall amount is defined as follows: - For each tower $j$, if and only if there exist towers $i$ and $k$ such that $l \le i \le j \le k \le r$, and both tower $i$ and tower $k$ are at least $x$ higher than tower $j$, i.e., $$ H_i - H_j \ge x \quad \text{and} \quad H_k - H_j \ge x, $$ then a column of water of height $x \ge 0$ can be stored on tower $j$. - Let $f(j)$ be the maximum possible height of the water column that can be stored on tower $j$. - The rainfall amount is defined as $$ f(l) + f(l+1) + \cdots + f(r), $$ i.e., the sum of the maximum water column heights that can be stored on these towers. Evirir is confident in the new generation of Malaysian OI contestants, so if you were only asked to compute the rainfall amount for one interval, that would be too easy. Instead, you need to process $Q$ operations, and each operation is one of the following two types: - Update: $0\ l\ r\ x$ --- add $x$ to $H_i$ for all $l \leq i \leq r$. - Query: $1\ l\ r$ --- output the rainfall amount of the tower interval $[l, r]$. Notes: - When answering a query for interval $[l, r]$, when computing $f(i)$ and the rainfall amount, you must not consider towers outside this interval. Towers outside the interval cannot be used to hold water. - Tower heights can be negative, but the rules remain the same. See the sample for related explanation.

The first line contains two integers $N$ and $Q$ separated by spaces. The second line contains $N$ integers $H_0, H_1, \ldots, H_{N-1}$ separated by spaces. The next $Q$ lines each describe one operation, containing several integers separated by spaces: - Update: $0\ l\ r\ x$ --- add $x$ to $H_i$ for all $l \le i \le r$. - Query: $1\ l\ r$ --- output the rainfall amount of the tower interval $[l, r]$.

For each query, output the rainfall amount of the towers in interval $[l, r]$ in order, one answer per line.

### Hint $\underline{Sample\ 1}$ This sample applies to subtasks 1, 5, and 6. There are $N = 9$ towers. Below is a visualization of the updates and queries: :::align{center}  ::: In the first query $\texttt{1 1 6}$, we consider towers $1$ to $6$. Look at tower $j = 5$ with height $1$. Tower $5$ can store a water column of height $1$, because: - Tower $i = 3$ has height $3$, which is $2$ higher than tower $5$. - Tower $k = 6$ has height $2$, which is $1$ higher than tower $5$. But tower $5$ cannot store a water column of height $2$, because there is no tower $k$ satisfying $j \le k \le 6$ whose height is at least $2$ higher than tower $5$ (i.e., height at least $1 + 2 = 3$). Note that you cannot take $k = 7$, because $k$ is not within the queried interval $[1, 6]$. Therefore, $f(5) = 1$, represented by the $1$ unit of water on tower $5$. In the second query $\texttt{1 0 8}$, we consider towers $0$ to $8$. Look at tower $j = 4$ with height $-1$. Tower $4$ can store a water column of height $6$, because the heights of tower $i = 0$ and tower $k = 7$ are both $5$, both $6$ higher than tower $4$. It can also be proven that $6$ is already the maximum possible height, so $f(4) = 6$. In the update $\texttt{0 1 4 2}$, the heights of towers $1$ to $4$ are all increased by $2$. In the update $\texttt{0 6 8 -4}$, the heights of towers $6$ to $8$ are all decreased by $4$. In the query $\texttt{1 6 6}$, note that even if a tower has a negative height, it still needs taller surrounding towers to store water. Note that by taking $i = j = k$, it is always possible to store at least a water column of height $0$ on a tower. $\underline{Sample\ 2}$ This sample applies to subtasks 1, 5, and 6. ### Scoring For all test cases, the input satisfies the following Constraints: - $1 \le N\leq 5 \cdot 10^6$ - $1 \le Q \leq 5 \cdot 10^4$ - For all $0 \le i \le N - 1$, $|H_i| \leq 10^7$ - For all updates and queries, $0 \le l \le r \le N - 1$ - For all updates, $|x| \leq 10^7$ - There is at least one query operation. | Subtask | Points | Additional Constraints | | :---: | :---: | :---: | | $1$ | $8$ | $N, Q \leq 1000$ | | $2$ | $8$ | $Q = 1$ | | $3$ | $16$ | $N \leq 10^6$ and there are no update operations in the input | | $4$ | $18$ | In updates, $l = r$ and $x > 0$, and in queries, $[l, r] = [0, N - 1]$ | | $5$ | $25$ | $N \leq 5 \cdot 10^5$ | | $6$ | $25$ | --- | Translated by ChatGPT 5