R01446
최대 구간 합
골드 I레이팅
의견: 0
설명
수열 \(A_1, A_2, \dots, A_N\)이 주어진다. 다음 두 종류의 연산을 처리하여라.
- 갱신 (타입 1): \(A_i\)를 \(v\)로 바꾼다.
- 구간 최대 부분합 (타입 2): 구간 \([l, r]\) 안에서 연속된 원소들의 합이 최대가 되는 부분 구간의 합을 구한다. 단, 부분 구간은 길이 \(1\) 이상이어야 한다.
각 타입 2 연산의 결과를 순서대로 출력하여라.
제약
- \(1 \le N \le 200\,000\)
- \(1 \le M \le Q \le 200\,000\)
- \(1 \le i \le N\), \(\;1 \le l \le r \le N\)
- \(-10^9 \le A_i, v \le 10^9\)
입력 형식
첫째 줄에 수열의 길이 \(N\), 타입 2 연산의 수 \(M\), 총 연산 수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 초기 수열 \(A_1, A_2, \dots, A_N\)이 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 걸쳐 연산이 주어진다.
1 i v— \(A_i\)를 \(v\)로 갱신한다.2 l r— 구간 \([l, r]\)의 최대 연속 부분합을 질의한다.
출력 형식
타입 2 연산마다 한 줄씩, 최대 연속 부분합을 출력한다.
예제 1
입력
5 3 4
2 -3 5 -1 4
2 1 5
2 2 4
1 2 6
2 1 5
출력
8
5
16
설명
배열 \([2, -3, 5, -1, 4]\)에서 구간 \([1,5]\) 최대 부분합은 \(5+(-1)+4=8\)이다. 구간 \([2,4]\) 최대 부분합은 \(5\)이다. \(2\)번 원소를 \(6\)으로 바꾸면 배열은 \([2,6,5,-1,4]\)이 되어 구간 \([1,5]\) 최대 부분합은 \(2+6+5+(-1)+4=16\)이 된다.
예제 2
입력
4 2 2
-5 -2 -8 -1
2 1 4
2 1 2
출력
-1
-2
설명
모든 원소가 음수이면 가장 큰 원소 하나가 최대 부분합이다. 구간 \([1,4]\)에서는 \(-1\), 구간 \([1,2]\)에서는 \(-2\)이다.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
최대 구간 합
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
최대 구간 합
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기