아이디어

• 먼저 가능성에 대해 알아보자.
  • 가장 naive한 반복: 시간 $O(Qn)$ → NO
  • 모든 $f_n(x)$ 메모이제이션: 시간 $O(Q)$ → OK, 공간 $O(mn)$ → NO
• 그렇다면 중간은 없나?
  • 2의 제곱수에 대해서만 $f_n(x)$를 저장해두자.
  • 찾아올 때는 $n=(\cdots d_2d_1d_0)_2$라 하면 초깃값을 $x$로 시작해서 각 자릿수 $d_k$가 1일 때 값에다 $f_{2^k}$를 적용하면 된다.
• 이때, 저장해둔 $f_{2^k}(x)$ 배열은 '희소 배열(sparse matrix)'라고 하는 자료구조다.
• 이 방법은 시간 $O(Q \lg n)$, 공간 $O(m \lg n)$을 가진다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int m, Q, n, x, ans;

    static int[][] st;    // sparce table

    public static void main(String[] args) throws Exception {
        m = Integer.parseInt(rd.readLine());

        // sparce table
        // st[0][x] = f_1(x), st[1][x] = f_2(x), st[2][x] = f_4(x), ... , st[b][x] = f_{2^b}(x)
        // f_n(x) = f_({...d_2d_1d_0}_2)(x) = (...(f_{2^d_2}(f_{2^d_1}(f_{2^d_0}(x)))...)
        // Note: 2^19 > 500_000 = max(n)
        st = new int[19][m+1];

        tk = new StringTokenizer(rd.readLine());
        for (int i=1; i<=m; i++) {
            st[0][i] = Integer.parseInt(tk.nextToken());
        }

        for (int k=1; k<=18; k++) {
            for (int i=1; i<=m; i++) {
                st[k][i] = st[k-1][st[k-1][i]]; // f_n(x) = f_{n/2}(f_{n/2}(x))
            }
        }

        Q = Integer.parseInt(rd.readLine());
        for (int i=0; i<Q; i++) {
            tk = new StringTokenizer(rd.readLine());
            n = Integer.parseInt(tk.nextToken());
            x = Integer.parseInt(tk.nextToken());

            ans = x;
            for (int j=0; j<=18; j++) {
                if (((n >> j) & 1) == 1) {
                    ans = st[j][ans];
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.println(sb);
    }
}

메모리 및 시간

• 메모리: 99964 KB
• 시간: 884 ms

리뷰

• 희소 배열 자료구조를 처음 배우고 적용해보았다.
• 세그먼트 트리랑 비슷한 부분도 있는 것 같다.