(17435) 합성함수와 쿼리

https://www.acmicpc.net/problem/17435

단계별로 풀어보기

47단계(최소 공통 조상) 2번째

 

 

 

LCA를 효율적으로 구할 수 있는 희소 테이블(Sparse Table)에 대해 알아보는 문제.

희소 테이블이란 정적 테이블에서 주어지는 구간 쿼리를 효율적으로 구할 수 있는 자료 구조로 전처리하는 시간복잡도와 공간복잡도는 O(N log N)이며, 멱등원 쿼리는 O(1), 결합 법칙 쿼리는 O(log N)에 처리할 수 있다.

둘의 차이점은 쉽게 말해 구간 중복 계산 허용 여부이다. 예를 들어 구간 [1,4]의 최솟값을 구한다면 [1,3]과 [2,4]의 최솟값을 각각 구하고 합쳐도 정답이 나오므로 O(1)에 계산할 수 있지만 [1,4]의 합을 구한다면 [1,3]과 [2,4]의 합을 구해서는 정답을 구할 수 없으므로 O(log N)에 계산할 수 있다.

 

이 문제에서 희소 테이블을 만드려면 음이 아닌 정수 i에 대해 k=2^i라고 하면 f_k(x)를 전부 미리 구해두는 것이다. 범위 50만<2^19이므로 0부터 18까지 19*m배열이면 충분하다.

f_2k(x)=f_k(f_k(x))이므로 이전 테이블의 결과를 두 번 적용시키는 것으로 이번 테이블의 값을 구할 수 있다.

희소 테이블 전처리가 끝났다면 입력 n이 들어왔을 때 n을 2의 거듭제곱 단위로 쪼개 희소 테이블에서 구한 함수 적용 결과를 적용시키면 각각의 쿼리를 O(log N)으로 끝낼 수 있다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int m, q;
  
  cin >> m;
  
  vector v(19, vector<int> (m+1));
  
  for(int i=1;i<=m;i++)  cin >> v[0][i];
  
  for(int i=1;i<19;i++){
    for(int j=1;j<=m;j++){
      v[i][j]= v[i-1][v[i-1][j]];
    }
  }
  
  cin >> q;
  
  while(q--){
    int n, x;
    
    cin >> n >> x;
    
    for(int i=0;i<19;i++){
      if(n&(1<<i))  x= v[i][x];
    }
    
    cout << x << "\n";
  }
  
  return 0;
}