주가 전광판
골드 I의견: 0
도시의 중심가에는 \(N\)개의 LED 주가 전광판이 일렬로 늘어서 있다. 왼쪽부터 차례로 \(1\)번부터 \(N\)번까지 번호가 매겨져 있으며, \(i\)번 전광판은 어떤 종목의 현재 등락 지수 \(a_i\)를 보여 준다. 지수는 음수가 될 수도 있다.
관제 센터에서는 다음 두 종류의 작업을 실시간으로 처리해야 한다.
- 갱신 : 어떤 전광판 한 개의 지수가 새 값으로 바뀐다.
- 조회 : 연속한 구간에 대해 지수의 합, 최솟값, 최댓값 중 하나를 즉시 보고한다.
총 \(Q\)개의 작업을 순서대로 처리한 결과를 출력하여라.
\(1 \le N, Q \le 100\,000\)
\(-10^9 \le a_i, v \le 10^9\)
첫째 줄에 전광판의 개수 \(N\)과 작업의 개수 \(Q\)가 공백으로 구분되어 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 주어진다.
이후 \(Q\)개의 줄에 각각 하나의 작업이 주어진다. 각 작업은 다음 네 가지 형식 중 하나이다.
1 i v: \(i\)번 전광판의 지수를 \(v\)로 바꾼다. (\(1 \le i \le N\))2 l r: 구간 \([l, r]\)의 지수 합을 출력한다.3 l r: 구간 \([l, r]\)의 지수 최솟값을 출력한다.4 l r: 구간 \([l, r]\)의 지수 최댓값을 출력한다. (\(1 \le l \le r \le N\))
조회 작업(2, 3, 4)이 주어질 때마다 그 결과를 한 줄에 하나씩 순서대로 출력한다.
5 5
3 -1 4 1 5
2 1 5
3 2 4
1 2 10
4 1 3
2 1 512
-1
10
23처음 구간 \([1,5]\)의 합은 \(3-1+4+1+5=12\). \([2,4]\)의 최솟값은 \(-1\). \(2\)번을 \(10\)으로 바꾼 뒤 \([1,3]\)의 최댓값은 \(10\), \([1,5]\)의 합은 \(23\)이다.
1 3
7
2 1 1
1 1 -3
3 1 17
-3원소가 하나뿐인 경우. 합은 \(7\), 갱신 후 최솟값은 \(-3\)이다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
주가 전광판
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
주가 전광판