편의점 매출 최고 연속 구간

문제

한 편의점은 개점 이후 N일 동안 매일의 순이익을 기록해 두었다. 1일부터 N일까지 i번째 날의 순이익은 정수 a_i이며, 재고 폐기나 행사 비용 때문에 음수일 수도 있다. 점주는 장부를 정리하면서 두 가지 작업을 번갈아 처리한다. 첫째, 1 i x 작업은 i번째 날의 순이익을 x로 고쳐 쓴다. 장부 오류를 바로잡는 일이다. 둘째, 2 l r 작업은 l일부터 r일까지 중에서 연속한 하루 이상의 기간을 골라 그 기간의 순이익 합을 최대로 만들었을 때의 합을 구한다. 고르는 기간은 반드시 l일 이상 r일 이하에 완전히 들어가야 하며, 비어 있는 기간은 고를 수 없다. 따라서 구간 안의 모든 날이 손실이면 가장 손실이 작은 하루의 값이 답이 되어 음수가 나올 수 있다. 작업이 주어진 순서대로 처리하면서, 2 l r 작업마다 구한 최댓값을 한 줄에 하나씩 출력하라. 2 l r 작업이 하나도 없으면 아무것도 출력하지 않는다.

입력

첫 줄에 두 정수 N, Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 1 ≤ Q ≤ 200000)
둘째 줄에 N개의 정수 a_1, …, a_N이 주어진다. (|a_i| ≤ 10^9)
다음 Q개의 줄에 각각 작업이 하나씩 주어진다. 작업은 "1 i x" 또는 "2 l r" 형식이다. 1 i x에서는 1 ≤ i ≤ N, |x| ≤ 10^9이고, 2 l r에서는 1 ≤ l ≤ r ≤ N이다.

출력

2 l r 작업마다 구한 최댓값을 입력 순서대로 한 줄에 하나씩 출력한다.

5 4
3 -2 5 -1 2
2 1 5
1 2 -10
2 1 5
2 2 2

7
6
-10

3 3
-4 -7 -1
2 1 3
1 3 -9
2 1 3

-1
-4

출처: Devin.KR 자체 제작