영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
The owner of the castle Drakfjälls Kastell is worried about a potential siege. If this happens, he wants the wall to be sturdy, so he plans to reinforce it. The castle wall consists of N wall segments arranged in a line. Each wall segment has a certain height. Below is an example of how the wall might look.
(그림은 원문 저장소에서 볼 수 있습니다)
The castle owner is also concerned about moisture damage when it rains, which could potentially worsen if he reinforces the wall. When it rains, all the wall's gaps will fill up with water, as long as the water cannot drain off at the sides. If it had rained on the previous example wall, water would have collected at the blue squares.
(그림은 원문 저장소에서 볼 수 있습니다)
To be strategic with his reconstruction, he wants to know how certain reinforcements would affect the amount of rainwater that collects in the wall if parts of it were destroyed in a siege. At his disposal, he has you, the castle's theoretical computer scientist. The castle owner will ask you two types of queries:
- Given two values l and r. If all wall segments are destroyed except those in the interval [l,r], how much rainwater would collect in the wall if it starts raining? Note that the wall isn't actually destroyed, so this doesn't affect future queries.
- Given two values i and w, increase the height of the ith wall segment by w. This is a permanent change that will affect future queries.
Input
The first line of input contains the integers N and Q (1 ≤ N, Q ≤ 2 · 10^5), the number of wall segments and the number of queries.
Then follow N integers h_1, h_2, …, h_N (1 ≤ h_i ≤ 10^9), the height of each wall segment.
The following Q lines describe all queries. Each query starts with an integer T, which is either 1 or 2.
- If T=1, it's followed by l, r (1 ≤ l ≤ r ≤ N). You should then output the answer to a type 1 query as described above.
- If T=2, it's followed by i, w (1 ≤ i ≤ N, 1 ≤ w ≤ 10^9). You should then increase the height of the ith wall segment by w. It's guaranteed that the height of the wall segment remains less than or equal to 10^9 after this.
Output
For each type 1 query, output the amount of water that collects if it starts raining after all wall segments outside the given interval are destroyed.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 13 | N, Q ≤ 1000 |
| 2 | 20 | All queries are of type 1. |
| 3 | 17 | h_i and w are chosen uniformly randomly among their valid values (See https://en.wikipedia.org/wiki/Discrete_uniform_distribution). |
| 4 | 23 | N, Q ≤ 70000 |
| 5 | 27 | No additional constraints. |
Explanation of Sample 1
In the first query, we're asked to calculate the amount of water that collects if we destroy everything outside [1,6]. Since [1,6] constitutes the entire wall, nothing is destroyed.
(그림은 원문 저장소에서 볼 수 있습니다)
In the second query, the Castle owner wants to know what happens if part of the right end of the wall is destroyed. The wall segments that would be destroyed are marked in dark gray.
(그림은 원문 저장소에서 볼 수 있습니다)
In the third query, part of the wall is raised. This affects the fourth query, which looks like the following.
(그림은 원문 저장소에서 볼 수 있습니다)
예제
예제 1
6 4 2 1 4 1 1 3 1 1 6 1 1 4 2 6 1 1 1 6
5 1 7
예제 2
6 4 3 2 1 3 2 4 1 1 6 2 3 3 1 2 6 1 1 4
4 3 1