BOJ 백준 19951: 태상이의 훈련소 생활

Table of contents

들어가며

걸린 시간: 1시간 (자력으로 풀지 못함)

문제를 읽고, N이 최대 10만이길래, query를 최적화하면 되겠거니 했습니다.

접근

근데 query에서의 시간 복잡도를 도저히 최적화를 하지 못하겠어서, 풀지 못했습니다.
태그를 까보니 누적합이었고, 사실 누적합인 걸 봐도 못 풀겠어서 인터넷에서 솔루션을 보고 이해를 했습니다.

구현

import sys

input = sys.stdin.readline
from bisect import bisect_left, bisect_right
if __name__ == "__main__":
    N, M = map(int, input().strip().split())
    HList = [0] + [*map(int, input().strip().split())]
    prefixSumList = [0 for _ in range(N + 1 + 1)]

    for _ in range(M):
        a, b, k = map(int, input().strip().split())
        prefixSumList[a] += k
        prefixSumList[b + 1] += -k

    for i in range(1, N + 1):
        prefixSumList[i + 1] += prefixSumList[i]

    for i in range(1, N + 1):
        print(HList[i] + prefixSumList[i], end = " ")