[baekjoon 19951] 태상이의 훈련소 생활 (누적합) (C++)

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

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

• 초기 연병장의 상태: 1 2 3 4 5 -1 -2 -3 -4 -5
• 첫 번째 지시 (1 5 -3)를 수행 한 뒤: -2 -1 0 1 2 -1 -2 -3 -4 -5
• 두 번째 지시 (6 10 5)를 수행한 뒤: -2 -1 0 1 2 4 3 2 1 0
• 세 번째 지시 (2 7 2)를 수행한 뒤: -2 1 2 3 4 6 5 2 1 0

초기 상태를 주고, x부터 y까지 덧셈할 값을 주고 최종 상태를 출력하는 문제이다.

N과 M은 10만 개로, 1~10만까지의 10만 개의 쿼리를 매번 더해주면 N^2으로 시간 초과가 날 것이다.

 

누적 합을 이용할 수 있는데, 쿼리를 다 저장해두었다가 마지막에 한꺼번에 상태를 업데이트해주는 것이다.

시작과 끝만 기록해놓고, 누적된 값을 한꺼번에 더하려는 방법을 사용했다.

 

처음엔 이 수가 끝인지, 시작인지 모르기 때문에 start와 end로 따로 저장해주어서 start를 만나면 total을 더해주고 이후에 end를 만나면 빼주었다.

1 2 3 4 5 -1 -2 -3 -4 -5
1 5 -3
6 10 5
2 7 2

값이 끝나는 구간은 그다음에 값을 빼줘야 한다. (1~5면 5까지 유효하고 6부터 없어진다)

5~6 구간 : 누적합이 -1이고 그다음에 5가 더해지고, -3이 끝나서 -(-3)이기에 -1 + 8 = 7이다.

7~8구간 역시 7까지는 2가 더해지고 8부터 없어진다.

#include <iostream>

using namespace std;

int n, m, arr[100001], from, to, weight, record[100001][2];

enum Tag {
	START,
	END
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i =1; i <= n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> from >> to >> weight;
		record[from][START] += weight;
		record[to][END] += weight;
	}

	int total = 0;
	for (int i = 1; i <= n; i++) {
		total += record[i][START];
		arr[i] += total;
		total -= record[i][END];
	}

	for (int i = 1; i <= n; i++)
		cout << arr[i] << " ";
}

 

그리고 풀고 나서 보니까, start와 end를 나눌 필요 없이

위의 방식대로 시작점을 기록해두고, 쿼리가 끝나는 점은 그 인덱스에 저장해주는 것이 아닌 그다음 인덱스에 -를 붙여서 저장해두면 1차원으로 해결할 수 있었다.

record[from] += weight;
t[to + 1] -= weight;

이후 1부터 누적으로 더해가면서 값을 갱신해주면 된다.