[BOJ] 최솟값과 최댓값

[BOJ] 최솟값과 최댓값

Problem URL : 최솟값과 최댓값

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
long long initMin(vector<long long>& a, vector<long long>& tree, int node, int start, int end) {
    if (start == end) {
        return tree[node] = a[start];
    } else {
        return tree[node] = min(initMin(a, tree, node * 2, start, (start + end) / 2),initMin(a, tree, node * 2 + 1, (start + end) / 2 + 1, end));
    }
}

long long getMin(vector<long long>& tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 2e9;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return min(getMin(tree, node * 2, start, (start + end) / 2, left, right),getMin(tree, node * 2 + 1, (start + end) / 2 + 1, end, left, right) );
}

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

long long getMax(vector<long long>& tree, int node, int start, int end, int left, int right) {
    if (left > end || right < start) {
        return 0;
    }
    if (left <= start && end <= right) {
        return tree[node];
    }
    return max(getMax(tree, node * 2, start, (start + end) / 2, left, right), getMax(tree, node * 2 + 1, (start + end) / 2 + 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> treeMin(tree_size);
    vector<long long> treeMax(tree_size);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }
    initMin(a, treeMin, 1, 0, n - 1);
    initMax(a, treeMax, 1, 0, n - 1);
    while (m--){
        int t1, t2;
        scanf("%d %d", &t1, &t2);
        printf("%lld %lld\n", getMin(treeMin, 1, 0, n - 1, t1-1, t2-1), getMax(treeMax, 1, 0, n - 1, t1 - 1, t2 - 1));

    }
    return 0;
}