P9912 [COCI 2023/2024 #2] Zatopljenje

Mr. Malnar has a topographic map that shows the elevation at each position in a certain area. Specifically, there are $n$ positions arranged in a line, and the $i$-th position is $h_i$ meters above sea level. Sea level may rise. You are given $q$ queries. For the $i$-th query, you need to answer: if sea level rises by $x_i$ meters, how many islands will form in the interval $[l_i, r_i]$? An island is defined as a maximal segment in which every position has height greater than $x_i$.  The figure above shows the first query of Sample 1 and the second query of Sample 2, respectively. In the left figure, there are two islands $[2,2]$ and $[4,5]$ in the interval $[2,5]$, while in the right figure there are four islands $[1,1]$, $[4,4]$, $[8,8]$, and $[10,10]$.

The first line contains two integers $n, q$. The second line contains $n$ integers $h_{1\sim n}$, representing the initial elevation of each position. The next $q$ lines each contain $3$ integers $l_i, r_i, x_i$, representing one query.

Output $q$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

### Constraints |$\text{Subtask}$|Score|Special Property| |:-:|:-:|:-:| |$1$|$10$|$n, q\le 2000$| |$2$|$20$|$l_i=1, r_i=n$| |$3$|$20$|There exists $p\in [1,n]$ such that $h_1\ge h_2\ge \cdots \ge h_p\le h_{p+1}\le \cdots \le h_n$| |$4$|$60$|None| For all testdata, $1\le n, q\le 2\times 10^5$, $0\le h_i, x_i\le 10^9$, $1\le l_i\le r_i\le n$. Translated by ChatGPT 5