마법 상점
골드 I의견: 0
왕국의 마법 상점에는 \(N\)개의 포션 칸이 일렬로 놓여 있다. 처음에는 모든 칸의 포션 파워가 \(0\)이다.
마법사는 \(Q\)번의 작업을 차례로 수행한다.
- 갱신 (타입 1): \(i\)번 칸의 포션 파워를 \(v\)로 바꾼다.
- 구간 합 질의 (타입 2): \(l\)번 칸부터 \(r\)번 칸까지의 포션 파워 합을 구한다.
각 타입 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\)
- \(0 \le v \le 10^9\)
- 각 쿼리의 정답은 \(10^{18}\) 이하임이 보장된다.
첫째 줄에 칸의 수 \(N\), 타입 2 질의의 수 \(M\), 총 작업 수 \(Q\)가 공백으로 구분되어 주어진다.
다음 \(Q\)개의 줄에 걸쳐 작업이 주어진다.
1 i v— \(i\)번 칸의 파워를 \(v\)로 갱신한다.2 l r— \(l\)번부터 \(r\)번까지 파워 합을 질의한다.
타입 2 질의마다 한 줄씩, 순서대로 구간 합을 출력한다.
5 2 5
1 3 10
1 5 7
2 1 5
1 3 4
2 2 5
17
11
처음에 모든 포션 파워는 \(0\)이다. 위치 \(3\)을 \(10\)으로, 위치 \(5\)를 \(7\)로 갱신한다. 구간 \([1,5]\) 합은 \(0+0+10+0+7=17\)이다. 위치 \(3\)을 \(4\)로 갱신하면 구간 \([2,5]\) 합은 \(0+4+0+7=11\)이 된다.
3 3 7
1 1 100
1 2 200
1 3 300
2 1 3
2 2 3
1 2 50
2 1 3
600
500
450
위치 \(1,2,3\)을 \(100,200,300\)으로 설정하면 구간 \([1,3]\) 합은 \(600\), \([2,3]\) 합은 \(500\)이다. 위치 \(2\)를 \(50\)으로 바꾸면 \([1,3]\) 합은 \(450\)이 된다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법 상점
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법 상점