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

풀이요약

누적합

풀이상세

1. 최대 NM 의 경우 백억이 나오므로 일반적인 반복문 풀이로는 풀리지 않는다.

2. sum 배열에 한하여 누적합을 실행한다. 예를 들어 범위의 시작과 끝이 $st,ed$ 라고 할 경우, 해당 범위 만큼 $+2$ 의 흙을 덮었다면 $ed+1$ 에서 부터는 $-2$ 만큼 파내면 누적합 시 동일한 결과가 나온다.

배운점

• 10만*10만은 1억이 아니라 100억이었음

#include <iostream>
using namespace std;
int N,M,st,ed,val;;
int arr[100000+4], sum[100000+4];
void input() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for(int i=1; i<=N; i++) {
        cin >> arr[i];
    }
    while(M--) {
        cin >> st >> ed >> val;
        sum[st] += val;
        sum[ed + 1] += (val * -1);
    }
}
void solve() {
    int acc = 0;
    for(int i=1; i<=N; i++) {
        acc += sum[i];
        cout << arr[i]+acc << " ";
    }
}
int main() {
    input();
    solve();
}