[백준 1280] 나무 심기

문제

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

 

알고리즘

세그먼트트리

 

풀이

나무 인덱스 순서대로 나무를 심어나갑니다. 나무를 심을 때 필요한 비용은 지금까지 심은 나무들과의 거리만큼이 필요합니다. 

 

먼저 떠오르는 풀이는 나무를 심을 때 마다, 지금까지 심은 나무들과의 거리를 일일이 탐색해 브루트 포스로 해결하는 것 입니다. 나무당 $O(N)$을 요구하므로 총 시간복잡도는 $O(N^2)$ 입니다. 역시 $N$의 최대는 20만이므로 시간초과 입니다. 하지만 펜윅트리를 활용하게 되면 나무당 쿼리를 $O(logN)$으로 줄일 수 있습니다. 

 

지금까지 심은 나무들은 총 두가지로 나눌 수 있습니다. 현재나무보다 왼쪽에 있는 나무들과 오른쪽에 있는 나무들 입니다. 각각의 정보를 구하기 위해서 필요한 정보는 다음과 같습니다. 첫번째는 갯수, 두번째는 거리 0부터 각 나무들까지의 거리의 합입니다. 즉 두 개의 펜윅트리를 이용해 두가지 정보를 얻으면 답을 얻을 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

const int MOD = 1000000007;
const int MX = 200005;

#define int long long
int N, x;
long long dist_tree[MX+1], cnt_tree[MX+1];
long long ans = 1;

void cnt_update(int idx, int val) {
    while (idx <= MX) {
        cnt_tree[idx] += val;
        idx += idx & -idx;
    }
}

void dist_update(int idx, int val) {
    while (idx <= MX) {
        dist_tree[idx] += val;
        idx += idx & -idx;
    }
}

int cnt_query(int idx) {
    int ret = 0;
    while (idx) {
        ret += cnt_tree[idx];
        idx -= idx & -idx;
    }
    return ret;
}

int dist_query(int idx) {
    int ret = 0;
    while (idx) {
        ret += dist_tree[idx];
        idx -= idx & -idx;
    }
    return ret;
}

signed main() {
    FAST;
    cin >> N;
    rep(i, N) {
        cin >> x;
        x += 1;
        int L = cnt_query(x);
        int R = i - L;

        int Ldist = (L * x - dist_query(x)) % MOD;
        int Rdist = (dist_query(MX) - dist_query(x) - R * x) % MOD;
        if (i >= 1) {
            ans = (ans * ((Ldist + Rdist) % MOD)) % MOD;
        }
        cnt_update(x, 1);
        dist_update(x, x);
    }

    cout << ans;
    return 0;
}