[백준-19951] 태상이의훈련소생활

+-누적합 문제이다.

값의 변경을 일일이 배열에 체킹해주면 터지게 된다. 때문에 이를 +-누적합을 통해 구해줄 수 있다.

• ground : 첫 값이 들어가있는 배열
• arr : "+ -" 체킹 배열
• sum : 최종적으로 몇 만큼 변경해야하는지 들어있는 배열

#include <cstdio>

using namespace std;
typedef long long LL;

int sum[100001];
int arr[100002];
int ground[100002];

int main() {
	int n, m, a, b, c;
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &ground[i]);
	}

	for (int i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &c);
		arr[a] += c;
		arr[b + 1] -= c;
	}

	for (int i = 1; i <= n; i++) 
		sum[i] = sum[i - 1] + arr[i];
	
	for (int i = 1; i <= n; i++) {
		ground[i] += sum[i];
		printf("%d ", ground[i]);
	}
	return 0;
}

https://www.acmicpc.net/problem/19951

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