사용자 도구

사이트 도구


ps:problems:boj:24505

blobhyperthink

ps
링크acmicpc.net/…
출처BOJ
문제 번호24505
문제명blobhyperthink
레벨플래티넘 4
분류

구간쿼리

시간복잡도O(nlogn)
인풋사이즈n<=10^5
사용한 언어Python 3.11
제출기록52812KB / 3088ms
최고기록2952ms
해결날짜2023/08/04

풀이

  • 불만 정렬를 더욱 확장시킨 문제. 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()

토론

댓글을 입력하세요:
R J K L Y
 
ps/problems/boj/24505.txt · 마지막으로 수정됨: 2023/08/04 01:37 저자 teferi