17435. 합성함수와 쿼리

17435번: 합성함수와 쿼리

---

쿼리 문제의 특징은 쿼리가 매우 많다는 점이다. 보통은 쿼리를 선형 시간보다 더 빠르게, 즉 로그 시간이나 상수 시간에 처리해야 한다. 이 문제 역시 쿼리의 수 Q가 20만, 합성 횟수 N이 50만으로 O(QN) 시간에 해결할 수 없다.

 

내가 지금까지 풀었던 쿼리 문제는 보통 쿼리를 로그 시간에 처리했다. 이번에도 로그 시간에 처리할 수 있을까?

 

전처리

다음의 배열을 생각하자.

$dp[i][x] \equiv f_{2^{i}}(x)$

$dp[i][x]$는 $f(x)$를 $2^{i}$번 합성한 값이다. 정의에 의해 $dp[i-1][x]$는 $f(x)$를 $2^{i-1}$번 합성한 값이다. 이 값을 $t$라고 하자. 그러면 $dp[i][x]$는 $f(t)$를 $2^{i-1}$번 합성한 값으로 나타낼 수 있다. 이 부분이 가장 중요하다. 어렵다면 직접 종이에 식을 써서 생각해 보자.

 

정리하면, 다음의 점화식을 이용하여 dp 테이블을 채울 수 있다.

$dp[0][x] = f(x)$
$dp[i][x]=dp[i-1][dp[dep-1][x]]$

---

이제 쿼리를 처리해야 한다. 위에서 $dp$의 첫 번째 인덱스에 로그를 사용했었다. 쿼리를 로그로 압축한 것이다. 따라서 압축을 해제할 때에는 지수를 사용해야 한다.

 

예를 들어 쿼리 $11, x$가 주어졌다고 하자. 쿼리에서는 $x$를 $11$번 합성한 값을 묻고 있다. 위에서 $2$의 지수 꼴로 압축한 값이 있으므로 이 값을 활용해야 한다. 따라서 우선 $x$를 $8$번 합성한 값 $y=dp[3][x]$를 찾고, $y$를 2번 합성한 값 $z=dp[1][y]$를 찾고, $z$을 1번 합성한 값 $ans=dp[0][z]$를 찾으면 된다. 

 

압축 과정을 정확히 이해했다면 압축 해제도 어렵지 않을 것이다. 과정을 일반화하면 다음과 같다.

$l=log_{2}(x)$라 하면, $query(n,x)=\begin{cases}dp[l][x] & (n=2^{l}) \\ dp[l-2^{l}][dp[l][x]] & (else) \end{cases}$

---

이 문제는 LCA 2와 사고방식이 매우 유사하다. 나도 LCA 2를 풀면서 '로그 압축' 방식을 알게 되었다.

 

그런데 solved.ac를 보니까 sparse array 태그가 붙어 있던데, 이건 뭐지? 나중에 한번 공부해 봐야겠다.