나무 심기

• x번째 나무를 심는 비용은. i=0…x-1에 대해서 sum(|p[x] - p[i]|) 이다. x번째 나무보다 왼쪽에 있는 나무들만 따로 모아서 p_l이라 하면 이것들의 비용은 p[x]*len(p_l) - sum(p_l) 이고, 오른쪽에 있는 나무들에 대한 비용은 sum(p_r) - p[x]*len(p_r)이다. 둘을 합하면 p[x]*len(p_l) - sum(p_l) + sum(p_r) - p[x]*len(p_r) 이고, 바꿔쓰면 sum(p)-2*sum(p_l) + p[x]-(i-2*len(p_l)) 이 된다.
• 이제 sum(p_l)과 len(p_l)을 빠르게 계산할수 있으면 해결된다. 좌표를 인덱스로 해서 count[pos] 와 dist[pos]를 저장하고 있으면 sum(dist[0:p[x])와 sum(count[0:p[x]) 의 구간합 쿼리로 계산할수 있고, 이것은 펜윅트리를 이용해서 구현가능하다.
• 나무 하나의 비용을 계산할때마다 O(1)번의 쿼리와 업데이트를 해주면 되므로, 총 시간복잡도는 O(n*logP)이다. (P는 좌표의 범위)

"""Solution code for "BOJ 1280. 나무 심기".

- Problem link: https://www.acmicpc.net/problem/1280
- Solution link: http://www.teferi.net/ps/problems/boj/1280

Tags: [Fenwick tree]
"""

import sys
from teflib import fenwicktree

MOD = 1_000_000_007


def main():
    N = int(sys.stdin.readline())
    X = [int(sys.stdin.readline()) for _ in range(N)]

    count_fenwick_tree = fenwicktree.FenwickTree(max(X) + 1)
    dist_fenwick_tree = fenwicktree.FenwickTree(max(X) + 1)
    dist_sum = 0
    answer = 1
    for i, x_i in enumerate(X):
        if i > 0:
            dist_sum_left = dist_fenwick_tree.query(0, x_i)
            count_left = count_fenwick_tree.query(0, x_i)
            answer *= dist_sum - dist_sum_left * 2 - x_i * (i - count_left * 2)
            answer %= MOD
        count_fenwick_tree.update(x_i, 1)
        dist_fenwick_tree.update(x_i, x_i)
        dist_sum += x_i
        
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree