[BOJ 10868 // C++] 최솟값

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 10868번 문제인 최솟값이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/10868

10868번: 최솟값

이 문제는 RMQ(Range Minimum Query)를 구현해보는 문제이다.

범용성이 높은 Segment Tree로 RMQ를 다음과 같이 구현해보았다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[100001];
int seg[262145];

int init(int L, int R, int sI) {
    if (L == R) return seg[sI] = arr[L];
    return seg[sI] = min(init(L, (L + R) / 2, sI * 2), init((L + R) / 2 + 1, R, sI * 2 + 1));
}

int query(int L, int R, int qL, int qR, int sI) {
    if (R < qL || qR < L) return 1000000007;
    if (qL <= L && R <= qR) return seg[sI];
    return min(query(L, (L + R) / 2, qL, qR, sI * 2), query((L + R) / 2 + 1, R, qL, qR, sI * 2 + 1));
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N, M; cin >> N >> M;
    
    for (int i = 1; i <= N; i++) cin >> arr[i];
    
    init(1, N, 1);

    for (int T = 0; T < M; T++) {
        int x, y; cin >> x >> y;
        cout << query(1, N, x, y, 1) << '\n';
    }
}