[Koistudy] 1396 - 눈 내리는 밤 (L) (C++ cpp)

문제 : koistudy-1396

 

 

풀이

  현재 n개의 영역의 눈 높이를 arr[i] 로 나타낸다고 해보자. arr[x]는 x 영역의 눈 높이이다.

그리고 F[i] = arr[i] - arr[i-1] 이라고 정의해보자.

 

  그렇다면 arr에 대한 [A, B] 구간을 W만큼 업데이트하는건 F[]로 따졌을 때 다음과 같다.

F[A] += W

F[B+1] -= W

왜냐하면 F[X] = F[X] - F[X-1] 이므로 F[A]와 F[B+1]을 제외하고는 변화가 없기 때문이다.

즉, 기존 range update가 point update로 변경된다.

 

  다음으로 arr[x]의 값을 알기 위한 쿼리는 F[1] + F[2] + ... + F[X] 로 나타낼 수 있다.

왜냐하면예를들어 X가 5일 경우

F[1] + F[2] + F[3] + F[4] + F[5] = arr[1] - 0 + arr[2] - arr[1] + arr[3] - arr[2] + arr[4] - arr[3] + arr[5] - arr[4] = arr[5]

처럼 되기 때문이다.

즉, 기존 point query가 range query로 변경된다.

 

  여기서 update는 최대 100만번, query는 최대 10만번이다. 따라서 더 횟수가 많은 update쪽을 point udpate로 변경한 것은 좋았으나, 10만번일지라도 range query를 하기엔 O(N^2) 이라 무리가 있어보인다. 근데 어차피 중간중간 query 하는게 아니고, update가 모두 끝난 후 최종적으로 출력하는데만 사용되고, F[1] + F[2] +... + F[X] 는 누적합에 해당한다.

 

  따라서 update가 모두 끝난 후 누적합을 한번 구해준 뒤 출력해주면 된다. 최종적으로 O(Q+N) 으로 풀 수 있다.

만약 이 문제보다 업그레이드 되서 쿼리 또한 중간중간 있었다면 segment tree - lazy propagation이나, 펜윅 트리로 '이 글'의 응용 2처럼 진행하면 O(QlogN) 정도로 가능할 것 같다.

 

 

코드 : github

#include <iostream>
using namespace std;
#define ll long long

int n;
ll arr[100002] = {0,};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> n >> q;

    while (q--) {
        int a, b, w;
        cin >> a >> b >> w;
        arr[a] += w;
        arr[b+1] -= w;
    }

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