Boj 23894) 합성함수와 쿼리 2

문제

백준 23894

설명

합성함수와 쿼리 문제의 버전업이다. 다행히도 f(1) 만 변하므로, 1 이 나오는 루프구간을 찾아서 이후 탐색 범위에서 제외시키면 평범한 희소배열 문제가 된다.

이때 다른 수에서 1로 가는 거리를 미리 저장해 놓으면 2~3 배 정도 더 빠르다. 이는 to1[] 이 최대 두번 호출되는 것도 있지만, 매번 while 문 내에서 1의 루프구간을 찾게되면 if 문 등으로 코드 자체가 느려지기 때문에 생기는 차이로 보인다.

시간 복잡도

O(\((\mathrm{N} + \mathrm{Q})\log{\mathrm{M}}\))

코드

int arr[31][200001], to1[200001];
int cur1;

int main()
{
	int n; cin >> n;

	for (int i = 1; i <= n; i++) cin >> arr[0][i];
	cur1 = arr[0][1]; arr[0][1] = 1; // arr[0][1] = 1 이어야지 추적할 수 있음. 그래서 arr[0][1] 백업. 
	
	// 희소배열 생성
	for (int j = 1; j < 31; j++)
		for (int i = 1; i <= n; i++)
			arr[j][i] = arr[j - 1][arr[j - 1][i]];
	
	// 특정 위치에서 1로 가려면 얼마나 걸리는지 계산
	for (int i = 2; i <= n; i++)
	{
		int cur = i, sum = 0;
		while (cur != 1 && sum <= 1e9) {
			int j = 0;
			while ((1 << j + 1) <= 1e9 && arr[j + 1][cur] != 1) j++;
			cur = arr[j][cur];
			sum += 1 << j;
		}
		if (cur == 1) to1[i] = sum;
	}
	
	int q; cin >> q;
	while (q--)
	{
		int c, m, x;
		cin >> c;
		if (c == 1) // f(1) = x
		{
			cin >> x;
			cur1 = x;
		}
		else { // f_m(x)
			cin >> m >> x;
	        
	        // 1로 보낼 수 있으면 보냄
			if (to1[x] && m >= to1[x]) {
				m -= to1[x];
				x = 1;
			}
	        
	        // 1로 보냈거나 원래 1이면
			if (x == 1)
			{
				// 다시 1로 돌아온다면 주기로 나머지처리
				if(to1[cur1]) m %= to1[cur1] + 1;
				
				// 1 을 넘길 수 있으면 다음으로 넘김
				if (m) { x = cur1; m--; }
			}
	
			// m > 0 이면 이제 1 나올일이 없으므로 평범한 희소배열 문제
			for (int i = 0; m; i++, m >>= 1)
				if (m & 0x1) 
	                x = arr[i][x];
	
			cout << x << '\n';
		}
	}
}