[BOJ] 백준 1280 나무 심기

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

 Input 

5 

3 4 5 6 7

　 

 Output 

180　

x 좌표에 나무를 심는 비용 = 현재 심어진 모든 나무와 거리

ex) [A] - [B] - [X] - [C] - [D] - [E]

▶ |X - A| + |X - B| + |C - X| + |D - X|+ |E - X| 

    심으려는 위치 X를 기준으로 앞/뒤로 계산식을 표현하면 다음과 같습니다.

    앞: 2 * X - (A + B)  → 앞쪽에 심어져 있는 나무의 갯수 * 심으려는 좌표 - (앞쪽에 심어져 있는 좌표의 합)

    뒤: (C + D + E) - 3 * X → (뒤쪽에 심어져 있는 좌표의 합) - 뒤쪽에 심어져 있는 나무의 갯수 * 심으려는 좌표

문제에서 요구하는 시간내에서 이를 구하기 위해서는 세그먼트 트리나 펜윈트리를 이용합니다.

→ 각 구간의 심어져 있는 나무 개수를 구현한 Tree (단말 노드 = 1)

→ 각 구간의 심어져 있는 좌표들의 합을 구현한 Tree (단말 노드 = 좌표)

※ 단말노드에 어떤 값을 두는지만 다르기 때문에 update(), query() 구현 자체는 동일합니다.

 

시뮬레이션

① [_] - [_] - [3] - [_] - [_] - [_] - [_]

    심는 비용 = 0

② [_] - [_] - [3] - [4] - [_] - [_] - [_]

    심는 비용 = 1 * 4 - 3 = 1 

    → ans = 1

③ [_] - [_] - [3] - [4] - [5] - [_] - [_]

    심는 비용 = 2 * 5 - 7 = 3 

    → ans = 1 * 3 = 3

④ [_] - [_] - [3] - [4] - [5] - [6] - [_]

    심는 비용 = 3 * 6 - 12 = 6 

    → ans = 3 * 6 = 18

⑤ [_] - [_] - [3] - [4] - [5] - [6] - [7]

    심는 비용 = 4 * 7 - 18 = 10 

    → ans = 18 * 10 = 180

 

* 해당 문제에 나무의 좌표는 서로 다르다는 보장이 없는 것을 주의해야 합니다.

 Input 

3 

1 2 1

　 

 Output 

1

- Tree 크기는 단말노드 * 4로 여유롭게 잡습니다.

※ 계산결과가 long long 범위인 것에 유의

    MOD 연산 처리 필요

---

#include <iostream>
using namespace std;
typedef long long LL;
const int LM = 200005;
const int MOD = 1000000007;
 
struct Node {
    LL val;
    int cnt;
 
    Node(LL _val = 0, int _cnt = 0) : val(_val), cnt(_cnt) {};
 
    Node operator = (const Node& x) {
        this->val = x.val;
        this->cnt = x.cnt;
        return *this;
    }
 
    Node operator + (const Node& x) {
        return Node(this->val + x.val, this->cnt + x.cnt);
    }
}tree[LM * 4];
LL ans = 1;
int X, N;
 
Node update(int now, int pos, int s, int e) {
    if (pos < s || pos > e) return tree[now];
    if (s == e)  return tree[now] = tree[now] + Node(pos, 1);
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    return tree[now] = update(L, pos, s, mid) +
        update(R, pos, mid + 1, e);
}
 
Node query(int now, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return Node(0, 0);
    if (s <= qs && qe <= e) return tree[now];
    int L = now * 2, R = L + 1, mid = (qs + qe) / 2;
    return query(L, s, e, qs, mid) + query(R, s, e, mid + 1, qe);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);
    
    // 첫번째 나무는 지출 비용없이 심습니다.
    scanf("%d", &X);
    update(1, X, 0, LM);
 
    // 2번째 나무부터 비용을 산출하고 나무를 심습니다.
    for (int i = 2; i <= N; ++i) {
        scanf("%d", &X);
        Node left = query(1, 0, (X - 1 < 0 ? 0 : X - 1), 0, LM);
        Node right = query(1, (X + 1 > LM ? LM : X + 1), LM, 0, LM);
        LL cost = ((LL)X * left.cnt - left.val + right.val - (LL)X * right.cnt) % MOD;
        ans = (ans * cost) % MOD;
        update(1, X, 0, LM);
    }
    printf("%lld\n", ans);
}