📝 문제 정보#
🧐 관찰 및 접근#
- 함수 $f$가 주어질 때, 최대 $500\,000$번 합성한 값을 구해야 한다.
- 나이브하게 계산하면 $O(QN)$으로 시간초과다.
- 전체를 전처리해두기엔, 공간복잡도가 $O(mN)$으로 너무 커진다.
- 따라서 적당히 전처리를 해두자.
- 이는 LCA에서 했던것과 같이, 희소 배열로 가능할 것 같다.
- 각 정의역에 대해 $1$번, $2$번, $4$번, $\cdots 2^k$번 합성한 결과를 저장해서 쿼리를 처리하자.
💻 풀이#
- 코드 (C++):
void solve(){
int N; cin >> N;
vector<vector<int>> f(20, vector<int>(N+1));
rep(i, 1, N+1) cin >> f[0][i];
rep(k, 1, 20) rep(i, 1, N+1) f[k][i] = f[k-1][f[k-1][i]];
int Q; cin >> Q;
while(Q--){
int n, x; cin >> n >> x;
rep(k, 0, 20) if(n & (1 << k)) x = f[k][x];
cout << x << "\n";
}
}