blobhyperthink

• 불만 정렬를 더욱 확장시킨 문제. 3개의 원소로 이루어진 튜플을 찾는 것이 10개로 늘어났지만, 기본 방법은 동일하다.
• 조건을 만족하면서 i번째 원소로 끝나는 l크기의 원소쌍의 갯수를 dp[l][i]이라고 하면, dp[l][..]을 dp[l-1][…]으로 부터 구하는 점화식은 dp[l][i] = sum_{j<i, A_j<A_i}(dp[l-1][j]) 처럼 된다. 저 sum부분을 세그트리 등을 이용해서 O(logn)에 구해주면, 전체 시간복잡도는 O(nlogn * 10) 이 된다

"""Solution code for "BOJ 24505. blobhyperthink".

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

Tags: [segment tree]
"""

import sys
from teflib import fenwicktree

MOD = 10**9 + 7


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]

    cur_counts = [1] * N
    for _ in range(10):
        cur_counts, prev_counts = [0] * N, cur_counts
        ost = fenwicktree.OrderStatisticTree(N + 1)
        for i, a_i in enumerate(A):
            cur_counts[i] = ost.count_less_than(a_i) % MOD
            ost.add(a_i, prev_counts[i])

    print(sum(cur_counts) % MOD)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.OrderStatisticTree