백준 17435 - 합성함수와 쿼리

문제

함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.

• f1(x) = f(x)
• f(n+1)(x) = f(fn(x))

예를 들어 f4(1) = f(f(f(f(1))))이다.

n과 x가 주어질 때 fn(x)를 계산하는 쿼리를 수행하는 프로그램을 작성하시오.

입력

첫 줄에 정수 m이 주어진다. (1 ≤ m ≤ 200,000)

다음 줄에 f(1), f(2), ..., f(m)이 차례대로 주어진다.

다음 줄에 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)

다음 Q개의 줄에 각각 정수 n과 x가 주어진다. (1 ≤ n ≤ 500,000; 1 ≤ x ≤ m)

출력

주어지는 n, x마다 fn(x)를 출력한다.

풀이 과정

https://readytojoin.tistory.com/entry/Sparse-Table-%ED%9D%AC%EC%86%8C-%EB%B0%B0%EC%97%B4?category=1193467

Sparse Table - 희소 배열

 

n의 제한이 최대 50만이고, 쿼리도 최대 20만이므로 하나하나 계산하는 것이 아닌 희소 배열에 대한 원리로 풀이할 수 있다. f(2^i)(x) 에 대한 정보를 계산하여 비트 연산을 활용해 합성함수 계산 시간을 줄인다.

# 17435. 합성함수와 쿼리 ( GOLD 1 )
import sys
input = sys.stdin.readline

m = int(input().rstrip())
arr = list(map(int, input().rstrip().split()))

# sparse_table
table = [[0 for _ in range(m + 1)] for _ in range(21)]
for i in range(m): table[0][i] = arr[i] - 1
for i in range(1, 21):
  for j in range(m):
    table[i][j] = table[i-1][table[i-1][j]]

q = int(input().rstrip())
for _ in range(q):
  n, x = map(int, input().rstrip().split())
  x -= 1
  for i in range(20, -1, -1):
    if n & (1 << i):
      x = table[i][x]

  print(x + 1)