주가 최대 연속 등락폭
골드 I의견: 0
어느 주식의 일별 등락폭 수열 \(a_1,\dots,a_N\)이 주어진다 (음수일 수 있다).
다음 두 명령을 처리하라.
U i x: \(i\)일째 등락폭을 \(x\)로 갱신한다.Q l r: 구간 \([l,r]\) 안에서 연속한 부분구간의 등락폭 합 중 최댓값을 구한다. (부분구간은 비어 있을 수 없으며 최소 길이 \(1\)이다.)
모든 Q 명령에 대한 답을 출력하라.
\(1 \le N, Q \le 100{,}000\), \(-10^6 \le a_i, x \le 10^6\), \(1 \le l \le r \le N\).
첫째 줄에 \(N\)과 \(Q\). 둘째 줄에 \(N\)개의 정수 \(a_i\). 이후 \(Q\)개의 줄에 명령이 주어진다.
각 Q 명령마다 한 줄에 최대 연속 부분합을 출력한다.
6 4
-2 1 -3 4 -1 2
Q 1 6
Q 4 6
U 3 5
Q 1 6
5
5
11\(Q\,1\,6\)의 최대 연속 부분합은 \(4+(-1)+2=5\). \(Q\,4\,6=4-1+2=5\). \(3\)번을 \(5\)로 바꾸면 \(1-3+\dots\)가 아니라 \(-3\to5\)이 되어 \(1+5+4-1+2=11\)이 최대.
4 3
-5 -2 -8 -1
Q 1 4
U 2 3
Q 1 4
-1
3모두 음수이면 가장 큰(절댓값이 작은) 한 원소가 답이다. 처음 \(-1\), \(2\)번을 \(3\)으로 바꾸면 \(3\).
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
주가 최대 연속 등락폭
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
주가 최대 연속 등락폭