BOJ 2357 최솟값과 최댓값

1 개요

BOJ 2357 최솟값과 최댓값

• 백준 온라인 저지 2357번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

struct SegmentTree {
    int n;
    vector<int> minTree, maxTree;

    SegmentTree(const vector<int> &array) {
        n = array.size();
        minTree.resize(4 * n);
        maxTree.resize(4 * n);
        build(array, 1, 0, n - 1);
    }

    void build(const vector<int> &array, int node, int start, int end) {
        if (start == end) {
            minTree[node] = maxTree[node] = array[start];
        } else {
            int mid = (start + end) / 2;
            build(array, 2 * node, start, mid);
            build(array, 2 * node + 1, mid + 1, end);
            minTree[node] = min(minTree[2 * node], minTree[2 * node + 1]);
            maxTree[node] = max(maxTree[2 * node], maxTree[2 * node + 1]);
        }
    }

    pair<int, int> query(int left, int right) {
        return make_pair(queryMin(1, 0, n - 1, left, right), queryMax(1, 0, n - 1, left, right));
    }

    int queryMin(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return INF;
        if (left <= start && end <= right) return minTree[node];
        int mid = (start + end) / 2;
        return min(queryMin(2 * node, start, mid, left, right), 
                   queryMin(2 * node + 1, mid + 1, end, left, right));
    }

    int queryMax(int node, int start, int end, int left, int right) {
        if (right < start || end < left) return -INF;
        if (left <= start && end <= right) return maxTree[node];
        int mid = (start + end) / 2;
        return max(queryMax(2 * node, start, mid, left, right), 
                   queryMax(2 * node + 1, mid + 1, end, left, right));
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<int> array(N);
    for (int &x : array) {
        cin >> x;
    }
    SegmentTree st(array);
    while (M--) {
        int a, b;
        cin >> a >> b;
        auto result = st.query(a - 1, b - 1);
        cout << result.first << ' ' << result.second << '\n';
    }
}