루미 알고리즘

#1625플래티넘Castle Wall

PO 2025 온라인 예선코딩출제 Arvid Kristoffersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
113N, Q ≤ 1000
220All queries are of type 1.
317h_i and w are chosen uniformly randomly among their valid values (See https://en.wikipedia.org/wiki/Discrete_uniform_distribution).
423N, Q ≤ 70000
527No 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

출처 표기

출처: Programmeringsolympiaden 2025년 온라인 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.