f(1), f(2), f(3), f(4) ··· f(m)이 주어지고 f1(x) = f(x), fn(x) = f(fn-1(x)) 이라고 했을 때 Q 번째의 fn(x)를 구하면 되는 문제입니다.
Q가 20만이고 n이 50만이 될 수 있으므로 O(Qn)의 시간 복잡도로 풀 수 없습니다.
f(x)을 n 번 찾을 경우 미리 알고 있을 경우에 시간을 줄일 수 있을 것입니다.
n, x 범위가 이차원 배열로 다 잡을 수 없는 범위이므로 희소 테이블 (sparse table)을 이용하겠습니다.
dp[x][k] = fk(x)로 문제를 해결하겠습니다.
이때 k를 1~n까지 저장을 하려면 메모리와 시간이 부족하기 때문에 2^0~2^k( <= n) 번째만 배열에 저장해주도록 하겠습니다.
예를 들어, dp[x][2] = f_4(x), dp[x][5] = f_32(x)를 저장하는 것입니다.
이렇게 되면 dp[x][k]를 구할 때 걸리는 메모리와 시간이 줄어들 수 있고 시간 복잡도는 O(Qlgn)입니다.
dp[x][k]를 구할 건데 지수법칙을 이용하겠습니다.
2^(x-1) + 2^(x-1) = 2^x을 이용하여 dp 식을 짤 수 있는데 dp[x][k] = dp[dp[x][k-1]][k-1]이라고 할 수 있습니다.
f_k(x) = f_k-1((f_k-1(x))
이렇게 먼저 dp를 구한 뒤 n, x가 주어지면 dp[n][x]가 주어지면 구할 수 있지만 x가 2k의 형태가 아니라면 dp에서 바로 값을 빼올 수가 없어 구해주셔야 합니다.
만약에 f_11(x)을 구한다고 하면 11은 이진수로 1011이므로 x부터 시작해서 1번, 2번, 8번을 가면 됩니다.
자세한 내용은 희소 테이블을 공부… (덤으로 LCA도…)
#include <cstdio>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef vector <int> vi;
typedef vector <vi> vvi;
#define MAX ((int)log2(500005))
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int m; cin >> m;
vvi dp(m + 1, vi(MAX + 1));
vi visit(m + 1);
for (int i = 1, x; i <= m; i++) {
cin >> x;
dp[i][0] = x;
}
for (int i = 1; i <= MAX; i++)
for (int j = 1; j <= m; j++)
dp[j][i] = dp[dp[j][i - 1]][i - 1];
int q; cin >> q;
while (q--) {
int a, b; cin >> a >> b;
for (int i = 0; i <= MAX; i++)
if (a & (1 << i)) b = dp[b][i];
cout << b << '\n';
}
return 0;
}