백준 17435 (합성함수와 쿼리) c++

문제

17435번: 합성함수와 쿼리

정의역과 공역 문제 입니다. 

m개의 정수가 주어지면 각 정수마다 f(1), f(2)....f(m)의 위치를 갖습니다.

쿼리의 갯수 Q가 주어지면 

Q개의 쿼리마다 정수 n과 x가 주어지면 

n번의 f(x) 연산을 한 값을 출력하면 되는 문제입니다.

 

naive하게 계산하면 총 O(n)번의 연산을 통해 계산 가능합니다.

하지만 m의 범위가(200000) 까지 이고 n의 범위가 (500000) 이므로 총 10^10 의 시간복잡도를 가져서

시간초과가 일어납니다.

 

따라서 sparst table 알고리즘을 활용할 수 있습니다.

핵심아이디어는 𝑓(𝑥)뿐만 아니라  𝑛=2^m 꼴인 𝑓𝑛(𝑥) 들을 저장해놓는 것입니다.

f[x][y] = 𝑓2^y(𝑥)를 저장하는 것입니다.

그러면 어떤 n에 대해서 𝑓𝑛(𝑥)을 구하기 위해서는 O(log n)만의 연산을 통해 구할 수 있게 됩니다.

x부터 y까지 7번의 f(x)를 통하면 도달할 수있습니다. 그렇게 되면 O(N)의 시간복잡도를 가집니다.

𝑛=2^m 꼴인 𝑓𝑛(𝑥) 들을 저장해놓으면 총 3번만 움직이면 y로 도달 할 수 있습니다.

---

먼저 주어진 m개의 정수들을 sparse table로 옮기는 전처리 과정이 필요합니다.

int m;
cin >> m;
for (int i = 1; i <= m; i++)
    cin >> arr[i][0];
for (int i = 1; i < 20; i++)
    for (int j = 1; j <= m; j++)
        arr[j][i] = arr[arr[j][i - 1]][i - 1];

4번째 줄을보면

예시로 m개의 정수가 {3, 3, 5, 4, 3} 이 들어왔다고 하면

arr[1][0] = 3  (f(1) = 3)

arr[2][0] = 3  (f(2) = 3)

arr[3][0] = 5  (f(3) = 5)

arr[4][0] = 4  (f(4) = 4)

arr[5][0] = 3  (f(5) = 3) 이됩니다.

arr[x][y] = f2^y (x) 이기 떄문입니다.

 

5-7번째 줄을 보면 sparse table을 만드는 과정입니다.

2^i 번째에 도달할려면 2^i-1을 2번 가면 됩니다.

예를 들어 i가 3일때 8번째 에 도달할려면 4번 건너 뛰는 것을 2번 하면 됩니다.

---

쿼리 함수 구간입니다.

int query(int n, int x) {
    for (int i = 19; i >= 0; i--) {
        if (n >= (1 << i)) {
            n -= (1 << i);
            x = arr[x][i];
        }
    }
    return x;
} 

3번째 줄을보면 n번 가야하는데 n이 2^i보다 크거나 같으면 그만큼 이동해 주시면 됩니다.

4번째 줄을보면 ndl 2^i 만큼 이동했으므로 n을 2^i 만큼 빼줍니다.

5번째 줄을보면 x를 2^i만큼 이동했으므로 x값을 갱신해 줍니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[200001][20];
int n, x;
int query(int n, int x);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int m;
    cin >> m;
    for (int i = 1; i <= m; i++)
        cin >> arr[i][0];
    for (int i = 1; i < 20; i++)
        for (int j = 1; j <= m; j++)
            arr[j][i] = arr[arr[j][i - 1]][i - 1];
 
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> n >> x;
        cout << query(n,x) << '\n';
    }
 
 
    return 0;
}
int query(int n, int x) {
    for (int i = 19; i >= 0; i--) {
        if (n >= (1 << i)) {
            n -= (1 << i);
            x = arr[x][i];
        }
    }
    return x;
}