[BOJ 17435 | C++] 합성함수와 쿼리 :: Sparse Table

• 문제 링크 : https://www.acmicpc.net/problem/17435
• 문제 태그 : 자료 구조, 희소 배열
• 참고 자료 : https://namnamseo.tistory.com/entry/Sparse-Table

Sparse Table

정말 설명을 잘해둔 글입니다..!

 

풀이

fn : {1, 2, ..., m}→{1, 2, ..., m}로 문제에서 정의했기 때문에 table의 행의 범위를 1-m으로 설정할 수 있었습니다. 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int tmp = 1;
    int k = 0;
    while (tmp < 500000) {
        tmp *= 2;
        k++;
    }

    int m;
    cin >> m;
    vector<vector<int>> table(k + 1, vector<int>(m + 1, 0));
    for (int i = 1;i <= m;i++) cin >> table[0][i];
    
    int q;
    cin >> q;

    for (int i = 1;i <= k;i++) {
        for (int j = 1;j <= m;j++) {
            table[i][j] = table[i - 1][table[i - 1][j]];
        }
    }
    

    auto query = [&](int n, int x) {
        for (int i =  k; i >= 0; i--) {
            if (n & (1 << i)) {
                x = table[i][x];
            }
        }
        return x;
    };
    
    while (q--) {
        int n, x;
        cin >> n >> x;
        cout << query(n, x) << '\n';
    }
}