[백준] 1280 나무심기

나무를 심는 비용을 다~~ 구해서 곱하는 문제다

비용은 지금 심는 나무와 현재 심어져있는 모든 나무까지의 거리의 합이다

이 문제는 펜윅트리를 2개 만들어서 풀 수 있다

하나는 나무가 (0~200000) 중 몇번째 좌표에 몇개가 있는지 아는 용도고

두번째는 (나무의 거리 X 수) 를 담아두는 트리다

어떤 좌표 X에 나무를 심는다고 가정하면 우리는 비용을 2가지 작업으로 구할 수 있다.

1) X보다 큰 좌표에 나무가 심어져 있을 때

 = (심어진 나무의 거리 합) - (현재 좌표)X(심어진 나무의 수)

2) X보다 작은 좌표에 나무가 심어져 있을 때

 = (현재 좌표)X(심어진 나무의 수) - (심어진 나무의 거리 합)

이렇게 하면 비용을 구할 수 있다!

트리로 만들어 두면 시간안에 충분히 할 수 있다!

근데 문제를 제대로 안읽으면 시간초과가 뜰 수 있따...!

좌표가 0부터 시작하기 때문에 문제를 잘 읽어야한다....!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 200020
#define ll long long
const ll mod = 1e9 + 7;
int n;
ll _sum(vector<ll>&tree, int x) {
    ll ret = 0;
    for (int i = x; i > 0; i -= (i&-i)) ret += tree[i];
    return ret;
}
ll sum(vector<ll>&tree, int s, int e) {
    if (s > e) return 0;
    return (_sum(tree, e) - _sum(tree, s - 1));
}
void update(vector<ll>&tree, int x, ll val) {
    for (int i = x; i <= MAXN; i += (i&-i)) tree[i] += val;
}
int main() {
    scanf(" %d", &n);
    vector<ll> a(n + 1,0), tree1(MAXN+1, 0), tree2(MAXN+1, 0), ans(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        ll x; scanf(" %lld", &x);
        x += 1;
        if (i == 1) {
            update(tree1, x, (ll)1);
            update(tree2, x, x);
        }
        else {
            ans[i] += sum(tree2, (int)x + 1, MAXN) - x*sum(tree1, (int)x + 1, MAXN);
            ans[i] += x*sum(tree1, 1, (int)x - 1) - sum(tree2, 1, (int)x - 1);
            ans[i] %= mod;
            update(tree1, x, 1);
            update(tree2, x, x);
        }
    }
    ll mul = 1;
    for (int i = 2; i <= n; i++) {
        mul *= ans[i];
        mul %= mod;
    }
    printf("%lld\n", mul);
}