백준 17435번: 합성함수와 쿼리 (C++)

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

17435번: 합성함수와 쿼리

---

Solved By: Sparse Table

 

함수 f가 주어졌을 때, {5, 4, 3, 2, 1}이라고 치면 f(1)은 1번 인덱스로 이동하라는 소리입니다. 허나, n은 500,000까지 주어질 수 있고, 쿼리의 수는 200,000까지 주어질 수 있습니다. 즉, O(NM)으로 시간 초과가 날 수 있습니다.

 

Sparse Table을 통해 O(MlogN)으로 줄여서 문제를 풀 수가 있습니다.

 

#include <iostream>
#include <vector>
#define MAX 500001
#define LOG_MAX 19
using namespace std;

int n, m;
int nextt[MAX][LOG_MAX];

int main(){
    cin >> m;
    for(int i = 1; i <= m; i++){
        cin >> nextt[i][0];
    }
    
    for(int j = 1; j < LOG_MAX; j++){
        for(int i = 1; i <= m; i++){
            nextt[i][j] = nextt[nextt[i][j - 1]][j - 1];
        }
    }
    
    vector<int> res;
    cin >> n;
    for(int i = 0; i < n; i++){
        int N, X; cin >> N >> X;
        
        for(int j = LOG_MAX - 1; j >= 0; j--){
            if(N >= (1 << j)){
                N -= (1 << j);
                X = nextt[X][j];
            }
        }
        
        res.push_back(X);
    }
    
    for(auto x: res) cout << x << '\n';
    return 0;
}