[최소 공통 조상 단계] 백준 17435번 합성함수와 쿼리

문제

함수 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)를 출력한다.

 

아이디어 

예를 들어 n = 6 이라고 하자.

그러면 f6(x) = fffff(f(x)) 이다.

이것을 6번 반복하면 당연히 시간초과.

6을 이진수로 변경하면 110 이고, 2^K 꼴의 반복 횟수에 대해 미리 저장하여 이를 활용하는 아이디어

110은 4(100) + 2(10) 이므로 4번의 결과를 알고 있고 2번의 결과를 알고 있으므로 4번 먼저 한 결과 => 2번 한 결과를 출력하면 됨.

 

n이 최대 50만이고 50만은 비트로 표현하면 0 ~ 18 까지로 해결 가능. 따라서 19 level로 지정하고

arr[i][j]를 숫자 i를 level j에서 만드는 경우라고 한다면 

arr[i][j] =  arr[arr[i][j-1]][j-1] 과 같다 . 숫자 i를 j-1단계에서 만든 것을 j-1단계로 감싼 것.

이렇게 arr를 완성시키면 j 가 0이면 0번째 비트, 1이면 1번째 비트....18번째 비트까지 다 구해짐.

 

물론 초기값으로 0번째 비트의 값을 입력 받아둬야 함.

입력값 n에대해 2의 거듭제곱 꼴이 몇번 발생하는 지 파악.

만약 홀수라면 우선 0을 반환해서 0번째 비트 값을 꺼내오게 함. 그 이후엔 n-1에 대해 조사하므로 

짝수가 된다.

6으로 시도 시에 우선 digit에 의해 1이 반환됨 10에 대해서 시도하는 것.

그리고 6과 5를 & 하면 4가 되어 2가 반환됨. 100에 대해 시도 하여 결과 반환가능

 

만약 5로 시도시 처음에 x로 arr[x][0]가 꺼내지고,

5에 대해 4로 &하면 4가되어 2가 반환 됨.  따라서 1 시도 하고 100 시도하여 출력

4가 된 n은 3과 &시에 0 이되므로 while이 끝난다.

 

 

#include <iostream>
#include<vector>
#include <algorithm>
#include<cmath>
#include<queue>
#include<map>
using namespace std;
const int level = 19;
const int MAX = 500001;
int arr[MAX][level];

int M, Q;

int digit(int n)
{
	int ret = 0;
	while (n % 2 == 0)
	{
		n /= 2;
		++ret;
	}
	return ret;
}
int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> M;
	for (int i = 1; i <= M; i++)
		cin >> arr[i][0];
	for (int j = 1; j < level; j++)
		for (int i = 1; i <= M; i++)
			arr[i][j] = arr[arr[i][j - 1]][j - 1];
	cin >> Q;
	for (int i = 0; i < Q; i++)
	{
		int n, x;
		cin >> n >> x;
		while (n)
		{
			x = arr[x][digit(n)];
			n &= (n - 1);
		}
		cout << x << "\n";
	}
	
}