https://www.acmicpc.net/problem/19951
길이가 n인 일차원 배열에 흙 높이가 저장되어있다.
a부터 b까지 k만큼 파내라/덮어라를 m번 수행한 후 흙 높이를 출력해야한다.
1부터 n까지 k만큼 파내라/덮어라를 m번 수행하는 것이 최악의 경우이고, n <= 100,000, m <= 100,000 이므로 100,000^2 번의 연산이 필요하다. 당연히 시간초과이다.
따라서 누적합을 이용한다. 누적합을 이용하게 되면 파내거나 덮는 명령의 복잡도가 O(1)가 되고 이 명령을 m번 수행하므로 O(m)이다. 그리고 실제로 값을 갱신할 때(누적합을 구한다) m번 덧셈이 필요하다. 따라서, 대략 2 * m 의 연산이면 답을 구할 수 있다.
초기 배열 상태와 누적합 배열 상태
3 1 4 3 0 -1 -3 -4
0 0 0 0 0 0 0 0
명령1: 1 4 -3
3 1 4 3 0 -1 -3 -4
-3 0 0 0 3 0 0 0
명령2: 3 7 2
3 1 4 3 0 -1 -3 -4
-3 0 2 0 3 0 0 -2
m이 2였을 경우, 위 상태에서 누적합 배열에서 누적합을 계산하면 된다.
3 1 4 3 0 -1 -3 -4
-3 -3 -1 -1 2 2 2 0
누적합 배열에 있는 값이 바로 갱신될 높이이다. 원래 높이에 더해주자.
3 1 4 3 0 -1 -3 -4
-3 -3 -1 -1 2 2 2 0
더한 결과(답):
0 -2 3 2 2 1 -1 -4
편의를 위해 누적합 배열의 크기를 하나 더 크게 잡았다.
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int ground[100000];
int suffix[100001];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> ground[i];
}
for (int i = 0; i < m; i++) {
int a, b, k;
cin >> a >> b >> k;
a--;
b--;
suffix[a] += k;
suffix[b + 1] -= k;
}
for (int i = 1; i < n; i++) {
suffix[i] += suffix[i - 1];
}
for (int i = 0; i < n; i++) {
ground[i] += suffix[i];
cout << ground[i] << " ";
}
return 0;
}