[BOJ] 백준 10868 최솟값

출처: https://www.acmicpc.net/problem/10868

 Input 

10 4

75

30

100

38

50

51

52

20

81

5

1 10

3 5

6 9

8 10

 

 Output 

5

38

20

5

배열의 특정 구간이 자주 변경되므로 세그먼트 트리(Segment Tree)를 이용합니다.

단말 노드를 제외한 세그먼트 트리에서는 자식 노드들의 최솟값들이 저장됩니다.

인덱스 범위를 벗어나는 경우에는 INF(큰 수)를 반환하게 합니다.

(특정 범위에서 최솟값을 query하기 때문에 INF를 반환해도 상관 없습니다.)

---

#include<iostream>
#include<vector>
#include<cmath>
#define INF 2e9
#define endl "\n"
using namespace std;
inline int min(int A, int B) { if (A < B) return A; return B; }
int N, M;
vector<int> arr, tree;
vector<pair<int, int>> cmdList;
void input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        int a; cin >> a;
        arr.push_back(a);
    }
    for (int i = 0; i < M; i++)
    {
        int a, b; cin >> a >> b;
        cmdList.push_back(make_pair(a, b));
    }
}
int Make_SegmentTree(int node, int start, int end)
{
    if (start == end)
    {
        tree[node] = arr[start];
        return tree[node];
    }
    int mid = (start + end) / 2;
    int L = Make_SegmentTree(node * 2, start, mid);
    int R = Make_SegmentTree(node * 2 + 1, mid + 1, end);
    tree[node] = min(L, R);
    return tree[node];
}
int Query(int node, int start, int end, int qLeft, int qRight)
{
    if (qRight < start || end < qLeft)
        return INF;
     
    if (qLeft <= start && end <= qRight)
        return tree[node];
    int mid = (start + end) / 2;
    int L = Query(node * 2, start, mid, qLeft, qRight);
    int R = Query(node * 2 + 1, mid + 1, end, qLeft, qRight);
    return min(L, R);
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
 
    input();
 
    int treeHeight = ceil(log2(N));
    int treeSize = (1 << (treeHeight + 1));
    tree.resize(treeSize);
    
    Make_SegmentTree(1, 0, N - 1);
    for (int i = 0; i < cmdList.size(); i++)
    {
        int qLeft = cmdList[i].first - 1;
        int qRight = cmdList[i].second - 1;
        cout << Query(1, 0, N - 1, qLeft, qRight) << endl;
    }
}