성벽

Drakfjälls Kastell의 성주는 잠재적인 공성전을 걱정하고 있다. 공성전이 벌어질 경우에 대비해 성벽을 튼튼하게 만들고자 하므로, 성벽을 보강할 계획이다. 성벽은 일렬로 배치된 $N$개의 성벽 구간으로 이루어져 있다. 각 성벽 구간에는 정해진 높이가 있다. 아래는 성벽의 모습에 대한 예제이다.

성주는 성벽을 보강하면 빗물이 올 때 습기로 인한 손상이 잠재적으로 더 심해질 수 있다는 점도 걱정하고 있다. 비가 오면 물이 양옆으로 빠져나갈 수 없는 한 성벽의 모든 틈이 물로 채워진다. 앞의 예제 성벽에 비가 내렸다면 파란색 칸에 물이 고였을 것이다.

재건을 전략적으로 진행하기 위해, 성주는 공성전에서 성벽의 일부가 파괴되었을 때 특정 보강이 성벽에 고이는 빗물의 양에 어떤 영향을 미치는지 알고 싶어 한다. 성주는 성의 이론 전산학자인 당신의 도움을 받을 수 있다. 성주는 당신에게 다음 두 가지 유형의 쿼리를 한다.

• 두 값 $l$와 $r$가 주어진다. 구간 $[l,r]$에 속한 성벽 구간을 제외한 모든 성벽 구간이 파괴되었다면, 비가 내리기 시작할 때 성벽에 빗물이 얼마나 고이는가? 성벽이 실제로 파괴되는 것은 아니므로 이후의 쿼리에는 영향을 주지 않는다는 점에 유의한다.

• 두 값 $i$와 $w$가 주어지면, $i$번째 성벽 구간의 높이를 $w$만큼 증가시킨다. 이는 이후의 쿼리에 영향을 미치는 영구적인 변경이다.

채점

여러 테스트 그룹으로 구성된 테스트 세트로 답안을 평가하며, 각 테스트 그룹에는 일정한 점수가 배정되어 있다. 각 테스트 그룹은 여러 테스트 케이스로 구성된다. 한 테스트 그룹의 점수를 얻으려면 그 테스트 그룹의 모든 테스트 케이스를 해결해야 한다.

그룹 | 점수 | 제한

$1$ |$13$| $N, Q \leq 1000$

$2$ |$20$| 모든 쿼리는 유형 $1$이다.

$3$ |$17$| $h_i$와 $w$는 각각의 유효한 값 중에서 균등 무작위로 선택된다 (https://en.wikipedia.org/wiki/Discrete_uniform_distribution 참고).

$4$ |$23$| $N, Q \leq 70000$

$5$ |$27$| 추가 제한이 없다.

입력의 첫째 줄에 성벽 구간의 개수와 쿼리의 개수를 나타내는 정수 $N$와 $Q$가 주어진다 ($1 \le N, Q \le 2 \cdot 10^5$).

그다음 각 성벽 구간의 높이를 나타내는 $N$개의 정수 $h_1, h_2, \dots, h_N$가 주어진다 ($1 \leq h_i \leq 10^9$).

이어지는 $Q$개의 줄에 모든 쿼리가 주어진다. 각 쿼리는 $1$ 또는 $2$인 정수 $T$로 시작한다.

• $T=1$이면, 뒤이어 $l, r$가 주어진다 ($1 \leq l \leq r \leq N$). 그러면 위에서 설명한 유형 $1$ 쿼리의 답을 출력해야 한다.

• $T=2$이면, 뒤이어 $i, w$가 주어진다 ($1 \leq i \leq N$, $1 \leq w \leq 10^9$). 그러면 $i$번째 성벽 구간의 높이를 $w$만큼 증가시켜야 한다. 이후에도 해당 성벽 구간의 높이가 $10^9$ 이하로 유지됨이 보장된다.

각 유형 $1$ 쿼리마다, 주어진 구간 밖의 모든 성벽 구간이 파괴된 뒤 비가 내리기 시작할 경우 고이는 물의 양을 출력한다.

첫 번째 쿼리에서는 $[1,6]$ 밖의 모든 것을 파괴할 경우 고이는 물의 양을 계산해야 한다. $[1,6]$이 성벽 전체를 이루므로 아무것도 파괴되지 않는다.

두 번째 쿼리에서 성주는 성벽 오른쪽 끝의 일부가 파괴되면 어떻게 되는지 알고 싶어 한다. 파괴될 성벽 구간은 짙은 회색으로 표시되어 있다.

세 번째 쿼리에서는 성벽의 일부가 높아진다. 이는 다음과 같은 모습을 다루는 네 번째 쿼리에 영향을 미친다.