\(N\)개의 정수로 이루어진 배열 \(a\)를 다음 연산에 대해 관리하여라.

1. \(1\ i\ x\) — \(a[i] = x\)로 설정한다.
2. \(2\ l\ r\) — 전부 \([l, r]\) 안에 들어가는 비어 있지 않은 연속 부분 배열의 최대 합을 출력한다.

• \(1 \le N, Q \le 100000\)
• \(-10^9 \le a[i], x \le 10^9\)

합에는 64비트 산술이 필요하다.

첫째 줄에 \(N\ Q\); 둘째 줄에 \(N\)개의 정수; 그 뒤로 \(Q\)개의 연산 줄이 주어진다.

2번 연산마다 최대 부분 배열 합을 한 줄에 하나씩 출력한다.

riseoj 작성

출처 Original