BOJ 20931 - 혹 떼러 갔다 혹 붙여 온다

BOJ - 혹 떼러 갔다 혹 붙여 온다

Sparse Table을 활용하는 문제로써, 기존에 사용하던 문제들과 색다른 Sparse Table의 정의를 사용한다.

$$ \begin{aligned} P_{k,\,i}&=\text{i 번째 노드의 }2^k\text{번 째 부모}\\ D_{k,\,i}&=\text{i 번째 노드의 }2^k\text{번 째 부모까지의 거리} \end{aligned} $$

이 테이블을 구성하고 쿼리하는 방법을 살펴본다.

구성하는 법

ad-hoc 쿼리에 대한 내용이다.

간단히 Sparse Table의 성질을 이용해 $O(logN)$ 에 해줄 수 있다.

$\qquad \Large P_{k,\,i}=P_{k-1,\,P_{k-1,\,i}}$

$\qquad \Large D_{k,\,i}=D_{k-1,\,i}+D_{k-1,\, P_{k-1, i}}$

쿼리하는 법

쿼리는 특이하게 $O(log^2N)$ 이 걸린다.

$D$ 에 대해서 계속 주어진 $L$ 이 몇 번째 $2^k$ 번째 조상까지 갈 수 있을지를 체크해줘야 한다.

$D_{k,\,i} \le L < D_{k+1,\,i}$ 를 만족하는 $k$ 를 찾았다고 할 때, $P_{k,\,i}$로 현재 노드를 변경해주고 $L \coloneqq L-D_{k,\,i}$ 하면 되는데, 여기서 새롭게 변경된 노드가 마지막 노드라는 것이 보장이 안되기 때문이다.

코드

int LOG = 20;  
  
void solve() {  
   int q;  
   cin >> q;  
  
   int last_ans = 0;  
   int M = 1;  
  
   // 2^k 번째 조상까지 가는데 걸리는 높이, 2^k 번째 조상  
   vector<vector<pi>> T(LOG, vector<pi>(q + 5));  
   vi len(q + 5);  
   len[0] = 2e18;  
  
   while (q--) {  
      string cmd;  
      cin >> cmd;  
      if (cmd == "query") {  
         int x, L;  
         cin >> x >> L;  
  
         int ans = x;  
         while (ans && len[x] <= L) {  
            int sl = L;  
            for (int k = LOG - 1; k >= 0; k--) {  
               if (T[k][ans].fi <= L) {  
                  // 2^k 번째 조상까지 가는것보다 L이 더 크다.  
                  L -= T[k][ans].fi;  
                  ans = T[k][ans].se;  
               }  
            }  
            if (L == sl) break;  
         }  
         cout << ans << endl;  
         last_ans = ans;  
      } else {  
         int k, L;  
         cin >> k >> L;  
         int parent = (k + last_ans) % M;  
         len[M] = L;  
  
         T[0][M] = {L, parent};  
         for (int k = 1; k < LOG; k++) {  
            pi cur = T[k - 1][M];  
  
            int cost = T[k - 1][M].fi + T[k - 1][T[k - 1][M].se].fi;  
  
            T[k][M] = {cost, T[k - 1][T[k - 1][M].se].se};  
         }  
         M++;  
      }  
   }  
}