[ 백준 ] 1280번 - 나무 심기 (C++)

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

1280번: 나무 심기

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

 

1. segmentTree를 두개 만들어서 하나에는 모든 좌표의 합을 저장하고, 나머지 하나에는 나무의 개수를 저장합니다.

 

2. idx를 입력 받으면 두 segmentTree를 업데이트 해주고, 0 ~ idx - 1과 idx + 1 ~ 200000까지의 좌표의 합과 나무 개수를 이용하여 모든 나무까지의 거리를 구합니다.

 

3. 현재 좌표의 왼쪽 나무들까지의 합을 구할 때는 현재 좌표 * 나무 개수 - 왼쪽 나무의 좌표들의 합으로 구하고, 오른쪽 나무들까지의 합을 구할 때는 오른쪽 나무의 좌표들의 합 - 현재 좌표 * 나무의 개수를 더해 구합니다.

 

4. ans에 3에서 구한 값을 곱해주고 1,000,000,007로 모듈러 연산을 한 값을 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
#define M 1000000007
 
using namespace std;
 
int N;
ll segTree[400002];
ll segTree2[400002];
ll ans = 1;
 
void updateTree(ll idx)
{
    ll temp = idx - 200001;
 
    while (idx != 0) {
        segTree[idx] += temp;
        segTree2[idx]++;
        idx >>= 1;
    }
}
 
pair<ll,ll> getTree(int l, int r)
{
    ll ret = 0;
    ll ret2 = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            ret2 += segTree2[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            ret2 += segTree2[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
 
    return { ret, ret2 };
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        ll idx;
        scanf("%lld", &idx);
        pair<ll, ll> temp;
        pair<ll, ll> temp2;
 
        updateTree(idx + 200001);
 
        if (i != 0) {
            if (idx == 0) {
                temp = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp.first - idx * temp.second) % M)) % M;
            }
            else if (idx == 200000) {
                temp = getTree(200001, 200001 + idx - 1);
                ans = ((ans % M) * ((idx * temp.second - temp.first) % M)) % M;
            }
            else {
                temp = getTree(200001, 200001 + idx - 1);
                temp2 = getTree(200001 + idx + 1, 400001);
                ans = ((ans % M) * ((temp2.first - idx * temp2.second + idx * temp.second - temp.first) % M)) % M;
            }
        }
    }
 
    printf("%lld", ans);
}