목차

Promotion Counting

ps
링크acmicpc.net/…
출처BOJ
문제 번호14446
문제명Promotion Counting
레벨플래티넘 3
분류

구간 쿼리

시간복잡도O(nlogn)
인풋사이즈n <= 100,000
사용한 언어Python
제출기록62272KB / 1132ms
최고기록1132ms
해결날짜2021/05/18

풀이

코드

"""Solution code for "BOJ 14446. Promotion Counting".

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

import sys
from teflib import fenwicktree
from teflib import ttree


def main():
    N = int(sys.stdin.readline())
    p = [int(sys.stdin.readline()) for _ in range(N)]
    compressed_p = [None] * N
    for i, x in enumerate(sorted(range(N), key=lambda x: p[x])):
        compressed_p[x] = i
    tree = [[] for _ in range(N)]
    for i in range(1, N):
        parent = int(sys.stdin.readline())
        tree[parent - 1].append(i)

    answers = [0] * N
    ost = fenwicktree.OrderStatisticTree(N + 1)
    root = 0
    for node, is_discovering in ttree.dfs(tree, root):
        proficiency = compressed_p[node]
        if is_discovering:
            answers[node] = -(ost.size() - ost.count_less_than(proficiency + 1))
            ost.add(proficiency)
        else:
            answers[node] += ost.size() - ost.count_less_than(proficiency + 1)

    print(*answers, sep='\n')


if __name__ == '__main__':
    main()