본문 바로가기

알고리즘

마법의 공동 장부

New Era · 2번Lv. 4구간 합

마법의 공동 장부

문제 설명

(주)캣네생선의 적립금은 마을에서 돈처럼 쓰입니다. 모두가 마법의 공동 장부를 나눠 가지고 있어서, 누가 장부에 적으면 모든 장부에 같은 내용이 바로 나타나기 때문입니다.

출정을 앞두고 대리인 No.1은 공동 장부에 '군자금' 쪽을 새로 펼쳤습니다. 1번부터 n번까지 마을이 한 줄로 적혀 있고, 처음에는 모든 마을의 군자금이 0입니다. 마을 사람들이 군자금을 보내 올 때마다 장부에 더해집니다.

전쟁 자금을 걱정하던 소울곰은 쉬지 않고 장부를 들여다봅니다.

"3번 마을부터 7번 마을까지 군자금이 얼마나 모여수과?"

장부에는 다음 두 가지 명령이 섞여서, 들어온 순서대로 적힙니다.

  • [1, i, x]: i번 마을의 군자금에 x를 더합니다.
  • [2, i, j]: i번 마을부터 j번 마을까지(i번과 j번 포함) 군자금의 합계를 구합니다.

마을 수 n과 명령 목록 commands가 주어질 때, [2, i, j] 명령의 답을 명령이 나온 순서대로 리스트에 담아 반환하세요. 합계는 그 명령이 나오기 전까지의 [1, i, x] 명령만 반영합니다.


제한 사항

  • 입력은 [n, commands] 형태입니다.
  • 1 ≤ n ≤ 200,000
  • 1 ≤ commands의 길이 ≤ 100,000
  • [1, i, x] 명령: 1 ≤ i ≤ n, 1 ≤ x ≤ 10,000 (정수)
  • [2, i, j] 명령: 1 ≤ i ≤ j ≤ n
  • [2, i, j] 명령은 한 개 이상 있습니다.
  • 명령이 많고 마을도 많습니다. 합계 명령마다 마을을 하나씩 더하면 시간 안에 끝나지 않을 수 있습니다.

입출력 예

입력출력
[5, [[1, 1, 3], [1, 3, 5], [2, 1, 3], [1, 2, 4], [2, 2, 5], [2, 4, 4]]][8, 9, 0]
[3, [[2, 1, 3], [1, 2, 7], [1, 2, 7], [2, 2, 2]]][0, 14]
[10, [[1, 10, 100], [1, 1, 50], [2, 1, 10], [1, 5, 30], [2, 2, 9], [2, 5, 10]]][150, 30, 130]

입출력 설명

첫 번째 예

명령마을 1~5의 군자금답
[1, 1, 3]3, 0, 0, 0, 0
[1, 3, 5]3, 0, 5, 0, 0
[2, 1, 3]3 + 0 + 5 = 8
[1, 2, 4]3, 4, 5, 0, 0
[2, 2, 5]4 + 5 + 0 + 0 = 9
[2, 4, 4]0

그래서 [8, 9, 0]을 반환합니다.

두 번째 예

첫 합계 명령이 나올 때는 아직 군자금이 하나도 들어오지 않아 0입니다. 그 뒤 2번 마을에 7이 두 번 더해져 14가 됩니다.

예시 테스트

#입력기대값
1[5, [[1, 1, 3], [1, 3, 5], [2, 1, 3], [1, 2, 4], [2, 2, 5], [2, 4, 4]]][8, 9, 0]
2[3, [[2, 1, 3], [1, 2, 7], [1, 2, 7], [2, 2, 2]]][0, 14]
3[10, [[1, 10, 100], [1, 1, 50], [2, 1, 10], [1, 5, 30], [2, 2, 9], [2, 5, 10]]][150, 30, 130]

입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 12개도 함께 채점해요.