백준: Class 6 - 2357

</br> 클래스 6 계속
</br>

2357: 최솟값과 최댓값

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

#include <bits/stdc++.h>
#define MAX 1000000007

using namespace std;

long long nums[100001];
vector< pair<int, int> > segtree;

pair<int, int> makeSeg(int a, int b, int now){
    if( a == b ){
        segtree[now].first = nums[a];
        segtree[now].second = nums[a];
        return segtree[now];
    }
    int mid = (a+b) / 2;
    pair<int, int> p1 = makeSeg(a, mid, now*2);
    pair<int, int> p2 = makeSeg(mid+1, b, now*2+1);
    segtree[now].first = min(p1.first, p2.first);
    segtree[now].second = max(p1.second, p2.second);
    return segtree[now];
}

int minSeg(int a, int b, int now, int l, int r){
    if( r < a || b < l ) return INT_MAX;
    if( l <= a && b <= r ) return segtree[now].first;
    int mid = (a+b) / 2;
    return min(minSeg(a, mid, now*2, l, r), minSeg(mid+1, b, now*2+1, l, r));
}

int maxSeg(int a, int b, int now, int l, int r){
    if( r < a || b < l ) return INT_MIN;
    if( l <= a && b <= r ) return segtree[now].second;
    int mid = (a+b) / 2;
    return max(maxSeg(a, mid, now*2, l, r), maxSeg(mid+1, b, now*2+1, l, r));
}

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

    int n, m;
    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }

    int h = ceil(log2(n));
    segtree.assign(1<<(h+1), pair<int, int>(INT_MAX, INT_MIN));
    makeSeg(0, n-1, 1);

    while( m-- ){
        int a, b;
        cin >> a >> b;
        a--; b--;
        cout << minSeg(0, n-1, 1, a, b) << ' ' << maxSeg(0, n-1, 1, a, b) << '\n';
    }

}

얘도 세그먼트 트리를 활용한다!! 페어로 최솟값, 최댓값을 저장했다
각 노드에 접근하는 방식은 동일하므로, 어떻게 처리할 지만 바꿔주면 된다
minSeg()에서 만약 현재 인덱스가 구간 밖이면 이 쪽이 골라지지 않게 INT_MAX를 리턴하고, 만약 구간 안이면 이미 구해진 값 그대로 리턴한다.
그게 아니면, 반으로 나눠서 최솟값을 골라 리턴한다.
</br>

---

좋다
</br>