레이팅 미적용It’s winter, it has never been colder, and Mr. Malnar is looking at his photos from
his last cruise on the Adriatic and recalls unforgettable moments. The TV is on in
the background, broadcasting news about the latest proposals for measures to slow
down sea level rise. Looking at his photos of the coast, Mr. Malnar asks himself
what the photos would have looked like if sea level had risen a certain amount.
There are so many pictures, and even more questions, so Mr. Malnar asks for your
help.
We imagine the coast as a sequence of \(n\) numbers \(h_{1}\), \(h_{2}\), . . . , \(h_{n}\), where the \(i\)-th number represents relief
height at the \(i\)-th point. Mr. Malnar has \(q\) queries, where the \(i\)-th query is as following: How many islands
would there \(be\) between the \(l_{i}-th\) and \(r_{i}-th\) point \(if\) the sea level rose \(by\) \(x_{i}\) meters?
The left image shows the first query \(of\) the first sample test case, and the right image shows the second
query \(of\) the second sample test case.
The left islands correspond \(to\) intervals [2, 2] and [4, 5].
The right islands correspond \(to\) intervals [1, 1], [4, 4], [8, 8] and [10, 10].
An island is defined as the maximal interval where every \(h_{i}\) is strictly greater than the sea level. A
maximal interval is one that cannot be extended in either direction while keeping the mentioned condition
true. Initially, the sea level is at 0 meters.
The first line contains integers \(n\) and \(q\) (\(1 \le n\), \(q \le 2 \cdot 10^{5}\)), the length of the sequence and the number of
queries.
The second line contains \(n\) integers \(h_{1}\), \(h_{2}\), . . . , \(h_{n}\) (\(0 \le h_{i} \le 10^{9}\)) that describe the relief of the coast.
In each of the next \(q\) lines there are three integers \(l_{i}\), \(r_{i}\) and \(x_{i}\) (\(1 \le l_{i} \le r_{i} \le n\), \(0 \le x_{i} \le 10^{9}\)) that
describe the \(i\)-th query.
In the \(i\)-th of the \(q\) lines print the answer to the \(i\)-th query. Each of the queries is independent of the
others.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 10점 | n, \(q \le 2 \cdot 10^{3}\) |
2 | 20점 | \(l\)\(i = 1\), r\(i = n\) for all \(i = 1\), 2, . . . , q |
3 | 20점 | There exists an integer \(p\) (\(1 \le p \le n\)) such that the following holds: \(h@@RISE_MATH_BLOCK_0@@p\) i \(h@@RISE_MATH_BLOCK_1@@p+1\) ≤· · · ≤\(h\)\(n\) |
4 | 60점 | No additional constraints. |
6 3
2 4 2 3 4 1
2 5 2
3 5 3
3 4 42
1
010 3
5 0 3 4 2 0 1 6 3 5
3 9 1
1 10 3
1 10 22
4
3Clarification of the first example:
The first query is shown in the left image in the task description, islands correspond to intervals [2, 2] and
[4, 5]. In the second query island corresponds to interval [5, 5]. In the third query there are no islands
because everything is under water.
Clarification of the second example:
In the first query islands correspond to intervals [3, 5] and [8, 9]. In the second query (shown in the right
image in the task description) islands correspond to intervals [1, 1], [4, 4], [8, 8] and [10, 10], while in the
third query islands correspond to intervals [1, 1], [3, 4] and [8, 10].