메모리: 97432 KB, 시간: 880 ms
자료 구조, 희소 배열
2023년 10월 18일 11:04:13
함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자.
- f1(x) = f(x)
- fn+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)를 출력한다.