희소 테이블(Sparse Table)

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

17435번: 합성함수와 쿼리

위의 문제를 풀기위해 사용되는 테크닉 입니다.

합성함수를 해결하기 위해 n번 반복하는 것이 아닌

미리 테이블을 만들어

특정원소에서 1번 갔을때, 2번갔을때, 4, 16, 32 ......

와 같이 이진수의 자리수만큼 이동했을때의 도착지들을 2차원 배열로 모두 만들어 놓는것 입니다.

 

예를들어 

f {1, 2, 3, 4} -> {2, 1, 4, 3}

라는 함수가 있을때

f(f(f(f(f(f(1)))))) 와 같은 6번 합성된 합성함수를 구하기 위해 우선 6을 이진수로 바꿉니다.

110

이제 위의 이진수에서 자리수가 1인것의 의미는 해당 수 만큼 숫자를 바꾸어 주면 되는 것입니다.

1을 4번(100) 옮기고 나온수를 2번(10) 옮기면 원하는 정답을 구할수 있는 것이지요.

1을 4번 옮기는 동작은 미리 만들어진 희소테이블에 의해 바로 알수 있습니다.

따라서 총 6번 걸리는 동작을 희소테이블을 이용함에따라 2번으로 줄일수 있는것 이지요.

 

위의 문제를 풀면서 다시 설명드리겠습니다.

 

//17435 - 합성함수와 쿼리
 
#include <iostream>
using namespace std;
 
int N, M;
int arr[200001][19];
 
void init()
{
    cin >> N;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i][0];
    for(int j = 1; j<19; ++j)
        for(int i = 1; i<=N; ++i)
            arr[i][j] = arr[arr[i][j-1]][j-1];
}
 
int digit(int n)
{
    int ret = 0;
    while(n%2 == 0)
    {
        n /= 2;
        ++ret;
    }
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    init();
    int K; cin >> K;
    int n, x;
    for(int i = 0; i<K; ++i)
    {
        cin >> n >> x;
        while(n)
        {
            x = arr[x][digit(n)];
            n &= (n-1);
        }
        cout << x << "\n";
    }
}

 

우선 코드를 보시면 희소 테이블을 위한 배열 arr가 200000*19 만큼 잡혀있는것을 볼수 있습니다.

행은 원소의 최대 개수가 20만이기 때문에 20만으로 잡은것이고,

열은 함수의 합성이 총 50만번 일어날수 잇기 때문에 lg50만의 유사값인 19로 잡은 것입니다.

arr[i][j] 의 의미는 i번쨰 원소를 2^j만큼 이동시켰을때의 결과 값을 가지고 있습니다.

따라서 arr[i][j] 는 arr[ arr[i][j-1] ][j-1] 로 초기화 시킬수 있습니다!!

(i가 2^j번만큼 이동하는 것은 i를 2^(j-1)만큼 이동시킨것을 다시 2^(j-1)번 이동시키는 것과 같기 떄문 입니다.)

 

초기화를 모두 시켜주고 나면, 이제 문제에서 요구하는 조건에 대한 답을 할수 있습니다.

x번째 원소를 n번만큼 합성된 함수에 넣은 결과값을 구하기 위해 n를 이진수로 바꾸었을때 자리수가 1인 얘들과 x값에 대해 희소테이블에서 찾은 다음, x값을 해당 배열에 저장되어 있던 값으로 계속 바꾸어주면 됩니다. n이 0이 되면(즉 이동이 끝나게 되면) 마지막에 갱신된 x의 값이 바로 x번째 원소를 n번만큼 합성함수 시킨 결과 값입니다.