수열과 쿼리 41

시간 제한5초메모리 제한1024 MB

요약

배열의 구간마다 A_i를 max(A_i, x)로 바꾸는 갱신과, 구간 안의 최대 부분합을 0 이상으로 맞춰 출력하는 질의를 처리합니다.

난이도: 어려움10점 중 8점
유형: 세그먼트 트리, 동적 계획법
정답자: 아직 제출이 없습니다

문제

길이가 $N$ 인 수열 $A_1, A_2, \ldots, A_N$ 이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

0 l r x: $l \le i \le r$ 인 모든 $i$ 에 대해 $A_i = \max(A_i, x)$ 를 배정한다.
1 l r: $\max(0, \max_{l \le u \le v \le r} (\sum_{i=u}^{v} A_i))$ 를 출력한다.

입력

첫 번째 줄에 수열의 길이 $N$ 과 쿼리의 수 $Q$ 가 주어진다.

두 번째 줄에 수열 $A$ 의 원소 $A_1, A_2, \ldots, A_N$ 이 주어진다.

이후 $Q$ 개의 줄에 위에서 설명한 쿼리가 주어진다.

출력

모든 1 l r 형태의 쿼리에 대해 정답을 한 줄에 출력하라.

제한

$1 \leq N \leq 100\,000$
$1 \leq Q \leq 200\,000$
$-10^9 \le A_i, x \le 10^9$
$1 \le l \le r \le N$

예제1

예제 1

입력

14 14
-3 2 1 -2 3 -4 3 -5 -1 -2 3 -5 1 5
1 3 9
0 1 14 -4
1 1 14
0 3 11 -1
1 2 8
0 3 10 -1
1 4 7
0 6 9 2
1 1 14
0 10 10 7
1 1 14
0 6 9 4
0 1 5 2
1 1 14

예상 출력