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

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

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

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

구성하는 법Permalink

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

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

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

Dk, i=Dk−1, i+Dk−1, Pk−1,i\qquad \Large D_{k,\,i}=D_{k-1,\,i}+D_{k-1,\, P_{k-1, i}}

쿼리하는 법Permalink

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

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

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

코드Permalink

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++;  
      }  
   }  
}

Tags:

Categories:

Updated:

Comments

You may also enjoy