Funcia
Lv.1arraydifference-arrayprefix-sum

구간마다 더해지는 적립금

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

회원 n명(번호 0부터 n - 1)의 적립금이 모두 0에서 시작합니다. 이벤트 기록 updates가 주어지는데, 각 기록 [l, r, v]는 l번부터 r번까지(양 끝 포함) 모든 회원의 적립금에 v를 더한다는 뜻입니다. v가 음수이면 적립금이 줄어듭니다.

모든 이벤트를 순서대로 적용한 뒤, 회원별 최종 적립금을 번호 순서대로 담은 배열을 반환하세요.

입출력 예

nupdatesresult
5[[1, 3, 2], [2, 4, 3], [0, 2, -2]][-2, 0, 3, 5, 3]
3[[0, 2, 1000000000], [0, 2, 1000000000], [0, 2, 1000000000]][3000000000, 3000000000, 3000000000]
1[[0, 0, -7]][-7]

입출력 예 설명

예 1 — 각 이벤트를 적용할 때마다 적립금은 다음과 같이 바뀝니다.

적용한 이벤트0번1번2번3번4번
처음00000
[1, 3, 2]02220
[2, 4, 3]02553
[0, 2, -2]-20353

예 2 — 합계는 32비트 정수 범위를 넘을 수 있습니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int, updates: int[][]) → long[]

제한 사항

  • 1≤1 \le n ≤200,000\le 200{,}000
  • 1≤1 \le updates.length ≤200,000\le 200{,}000
  • updates[i] = [l, r, v], 0≤l≤r<0 \le l \le r < n, −109≤v≤109-10^9 \le v \le 10^9
  • 최종 적립금은 64비트 정수(long) 범위 안에 있습니다.

기대 복잡도

시간
O(N + Q)
공간
O(N)

입출력 예

nupdates기대 출력
5[[1,3,2],[2,4,3],[0,2,-2]][-2,0,3,5,3]
3[[0,2,1000000000],[0,2,1000000000],[0,2,1000000000]][3000000000,3000000000,3000000000]
1[[0,0,-7]][-7]

힌트

힌트

구간 전체에 값을 더하는 대신 **"여기서부터 v가 더해지기 시작하고, 여기서 끝난다"**는 표시만 남기세요.

  • diff[l] += v
  • diff[r + 1] -= v (r + 1 < n일 때)

모든 이벤트를 표시한 뒤 diff를 앞에서부터 누적하면, 누적값이 바로 각 회원의 최종 적립금입니다. 이런 배열을 차분 배열이라고 합니다. 누적값은 64비트 정수로 관리하세요.

복잡도 목표

이벤트마다 l부터 r까지 직접 더하면 O(N×Q)O(N \times Q)로 시간 초과입니다. 차분 배열을 쓰면 O(N+Q)O(N + Q)입니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)284 ms추정
C++ (GCC, gnu++23)284 ms도출됨
Python 3.131000 ms도출됨
Java 252014 ms도출됨
Kotlin 2.4 (JVM)1568 ms추정
C# 14 (.NET 10)1568 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.