백준 1280

1280번: 나무 심기

 

  현재 심는 나무 위치 기준으로 왼쪽, 오른쪽 나눠서 생각한다. 왼쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 왼쪽에 있는 나무의 개수 * (현재 위치) - 왼쪽 나무의 거리합이고 오른쪽에 있는 모든 나무와 현재 새로 심을 나무의 거리 차이의 합은 오른쪽에 있는 나무의 거리합 - (현재 위치) * 오른쪽에 있는 나무의 개수이다.

 

 주의점은 같은 곳에 나무를 여러 번 심을 수 있다는 점. 오버플로우를 주의해야 한다는 점. % 연산과 * 연산의 순위가 같기 때문에 괄호 잘 쳐야된다는 점. 첫 번째 나무를 심을 때는 곱을 하면 안 된다는 점 등이 있다. 필자는 첫 번째 나무를 심은 경우를 넘기기 위해 거리합이 0인 경우를 다 넘겼는데, 이것 때문에 2시간 동안 삽질했다. 거리 % MOD가 0인 경우 있는데, 이를 같이 넘겨버린 것. 이걸 생각 못하고 내 논리에 문제가 없는데 왜 틀렸냐며 반례를 찾아다녔다 ㅎㅎ 내 혈압

 

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MOD = 1e9 + 7;

ll cntT[1 << 21], distT[1 << 21];
ll base, n;

void update(ll k) {
    k += base;
    cntT[k]++;
    distT[k] += (k - base);
    for (k /= 2; k > 0; k /= 2) {
        cntT[k] = cntT[2 * k] + cntT[2 * k + 1];
        distT[k] = distT[2 * k] + distT[2 * k + 1];
    }
}

ll dist(ll a, ll b) {
    a += base; b += base;
    ll res = 0;
    while (a <= b) {
        if (a % 2 == 1) res += distT[a++];
        if (b % 2 == 0) res += distT[b--];
        a /= 2; b /= 2;
    }
    return res;
}

ll cnt(ll a, ll b) {
    a += base; b += base;
    ll res = 0;
    while (a <= b) {
        if (a % 2 == 1) res += cntT[a++];
        if (b % 2 == 0) res += cntT[b--];
        a /= 2; b /= 2;
    }
    return res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> n;
    for (base = 1; base < 200001; base *= 2);
    
    ll ans = 1;
    for (int i = 0; i < n; i++) {
        ll t; cin >> t;
        ll cur = (t * cnt(0, t - 1) - dist(0, t - 1)) + (dist(t + 1, 200000) - t * cnt(t + 1, 200000));
        update(t);
        if (i == 0) continue;
        ans = ((ans % MOD) * (cur % MOD)) % MOD;
    }
    cout << ans;
    return 0;
}