백준 17435 - 합성함수와 쿼리 (Python)

sparse table을 활용하는 문제입니다.
sparse table은 모든 계산값을 저장하는 것이 아니라 배로 늘어나는 값들만 저장시켜 계산하기 편하게 해주는 자료구조입니다.

전체 코드

import sys

input = sys.stdin.readline

m = int(input())
f = [0] + list(map(int, input().split()))
dp = [[f[i]] for i in range(m + 1)]

for i in range(1, 19):
    for j in range(1, m + 1):
        dp[j].append(dp[dp[j][i - 1]][i - 1])

for _ in range(int(input())):
    n, x = map(int, input().split())

    for i in range(18, -1, -1):
        if n >= 1 << i:
            n -= 1 << i
            x = dp[x][i]

    print(x)