백준17435 합성함수와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/17435

사용 알고리즘

  • sparse table

시간복잡도

  • 쿼리당 O(log N)

풀이

LCA를 구하는 방법을 생각해보면, 어떤 정점의 2^i번째 부모들을 미리 구해놓고 lifting을 해줬습니다.

이 문제도 비슷하게 2^k꼴인 모든 i에 대해 fi(x)를 미리 구해놓으면 log복잡도에 답을 구할 수 있습니다.
이런 자료구조를 sparse table이라고 부릅니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll dp[505050][22];
int n, q;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> dp[i][0];

	for(int j=1; j<22; j++)
        for(int i=1; i<=n; i++)
            dp[i][j] = dp[ dp[i][j-1] ][j-1];

	cin >> q;
    while(q--){
        ll n, x; cin >> n >> x;
        for(int i=0; n; i++){
        	if(n & 1) x = dp[x][i];
        	n >>= 1;
		}
        cout << x << "\n";
    }
}