불만 정렬

• 일반적인 2개의 원소로 정의되는 Inversion Counting을 좀 더 확장해서, 3개의 원소로 이루어진 inversion을 찾는 문제이다. BST를 이용해서 inversion을 찾는 방법을 조금 변형해서 적용하면 된다.
• 현재 원소보다 앞에 나온 원소들 중에서 값이 더 큰 원소들은 현재 원소와 inversion을 만들게 되는 것과 동일한 방식으로, 현재 원소보다 앞에 나온 원소들로 만들어진 inversion중에서 현재 원소보다 값이 더 큰것들은 3-원소 inversion을 만들게 된다.
• 이 아이디어를 구현하려면 우선 원소들을 저장하는 OrderStatisticTree와 inversion을 저장하는 OrderStatisticTree를 따로 만든다.
• 원소들을 순서대로 스캔하면서, 원소BST에서 현재 원소 x보다 값이 큰 원소의 갯수를 세어서 x를 포함하는 2-원소 inversion의 갯수를 세고, 원소 OrderStatisticTree에 x를 추가하는 것은 동일하다.
• 여기에 추가적으로, inversion BST에서 현재 원소 x보다 키값이 큰 inversion의 갯수를 세면 x를 포함하는 3-원소 inversion이 된다. inversion OrderStatisticTree에는 x를 포함하는 2-원소 inversion을 갯수만큼 추가한다.
• 이 과정에서 얻은 3-원소 inversion의 갯수를 모두 더한 것이 답이 된다.
• inversion OrderStatisticTree에서는 한번에 O(n)개의 inversion이 더해질수 있으므로, 일반 OrderStatisticTree보다는 펜윅트리 기반의 OrderStatisticTree를 사용하는 것이 필요하다. 그렇게 하면 각 원소들마다 처리해야할 작업은 O(logn)이 걸리고, 이것을 n개의 원소에 대해서 처리하므로 총 O(nlogn)에 해결 가능하다.
• 다른 풀이로는, 세 원소쌍에서 가운데에 있는 원소를 중심으로 생각하는 방법도 있다. 어떤 원소 x를 중간으로 하는 3-inversion의 갯수는, {x보다 앞에 나오면서 값이 더 큰 원소의 갯수} * {x보다 뒤에 나오면서 값이 더 작은 원소의 갯수}가 된다. {x보다 앞에 나오면서 값이 더 큰 원소의 갯수}는 그냥 2-inversion을 구하는 방식으로 구할수 있고, {x보다 뒤에 나오면서 값이 더 작은 원소의 갯수}는 뒤에서부터 스캔하면서 똑같은 방법을 적용하면 구할 수 있다. 이렇게 두번 스캐하면서 모든 x에 대해서 {x보다 앞에 나오면서 값이 더 큰 원소의 갯수}와 {x보다 뒤에 나오면서 값이 더 작은 원소의 갯수}를 구한 뒤에 각각을 곱한 값을 모두 더해서 구하더라도 O(nlogn)으로 해결된다. 구현은 해보지는 않았다.

"""Solution code for "BOJ 5012. 불만 정렬"

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

from teflib import fenwicktree


def main():
    N = int(input())
    a = [int(x) for x in input().split()]

    nums = fenwicktree.OrderStatisticTree(N)
    inversions = fenwicktree.OrderStatisticTree(N)
    answer = 0
    for a_i in reversed(a):
        answer += inversions.count_less_than(a_i)
        inversion_count = nums.count_less_than(a_i)
        inversions.add(a_i, inversion_count)
        nums.add(a_i, 1)

    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree