[백준] 2357번 최솟값과 최댓값

[적용한 알고리즘]

세그먼트 트리

 

[아이디어]

내용

 

[생각의 흐름 / 절차] 

내용

 

[교훈]

세그먼트 트리 응용을 풀러 가야겠다.

더 간단하게 풀 수 있을 거 같은데..

 

<코드>

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

long long construct_min(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start];
    }
    else {
        int mid = (start + end) / 2;
        return tree[node] = min(construct_min(a, tree, node * 2, start, mid), construct_min(a, tree, node * 2 + 1, mid + 1, end));
    }
}
long long construct_max(vector<long long> &a, vector<long long> &tree, int node, int start, int end){
    if (start == end){
        return tree[node] = a[start];
    }
    else {
        int mid = (start + end) / 2;
        return tree[node] = max(construct_max(a, tree, node * 2, start, mid), construct_max(a, tree, node * 2 + 1, mid + 1, end));
    }
}

//left : 구하고 싶은 범위의 시작, right : 구하고 싶은 범위의 끝
long long SegmentTree_min(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start){
        return 1000000001;
    } // 범위를 벗어날 때
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return min(SegmentTree_min(tree, node * 2, start, mid, left, right), SegmentTree_min(tree, node * 2 + 1, mid + 1, end, left, right));
}

long long SegmentTree_max(vector<long long> &tree, int node, int start, int end, int left, int right){
    if (left > end || right < start){
        return -1;
    } // 범위를 벗어날 때
    if (left <= start && end <= right){
        return tree[node];
    }
    int mid = (start + end) / 2;
    return max(SegmentTree_max(tree, node * 2, start, mid, left, right), SegmentTree_max(tree, node * 2 + 1, mid + 1, end, left, right));
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<long long> a(n);
    int h = (int) ceil(log2(n));
    int tree_size = (1 << (h + 1));
    vector<long long> tree_min(tree_size);
    vector<long long> tree_max(tree_size);

    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    construct_min(a, tree_min, 1, 0, n - 1);
    construct_max(a, tree_max, 1, 0, n - 1);

    while (m--){
        int x, y;
        scanf("%d %d", &x, &y);
        printf("%lld %lld\n", SegmentTree_min(tree_min, 1, 0, n - 1, x - 1, y - 1), SegmentTree_max(tree_max, 1, 0, n - 1, x - 1, y - 1));
    }

    return 0;
}