• 오일러 경로 테크닉과 구간 Rank 쿼리를 결합한 문제. 추가적으로 구간압축이 필요한 정도를 제외하면트리와 색깔와 거의 동일한 방식으로 풀린다.
• 각각의 서브트리에 대해서, 서브트리의 루트보다 큰 값을 갖는 노드의 갯수를 구하면 된다. X보다 큰 값의 갯수를 구하는 구간 Rank 쿼리는 오프라인 쿼리를 이용해서 구하면 되고, 이 방법을 쓰면 트리를 DFS로 한번 순회하면서 모든 쿼리에 대한 답을 구할수 있다. 좀더 자세한 설명은 트리와 색깔 참고
• 좌표 압축에 O(nlogn), 오일러 경로 테크닉(DFS)에 O(N), n번의 삽입 연산과, n번의 구간 rank 쿼리를 처리하는 데에 O(nlogn), 총 시간 복잡도는 O(nlogn)이 된다

"""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()

• Dependency: teflib.fenwicktree.OrderStatisticTree, teflib.ttree.dfs