[C++][백준 2357] 최솟값과 최댓값

문제

접근 방법

세그먼트 트리를 이용해서 구간의 최소, 최댓값을 구하는 문제이다.
최소, 최댓값 트리 초기화, 최소, 최댓값 찾기 이렇게 4개의 함수를 구현하면 된다.

pair와 같이 2개의 자료형을 저장해주는 것으로 트리를 구성하면 2개의 함수로 해결된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> numV;
vector<pair<int, int>> tree;
pair<int, int> init(int start, int end, int node)
{
    if (start == end)
        return tree[node] = {numV[start], numV[start]};
    int mid = (start + end) >> 1;
    pair<int, int> leftVal, rightVal;
    leftVal = init(start, mid, node << 1);
    rightVal = init(mid + 1, end, (node << 1) + 1);
    return tree[node] = {min(leftVal.first, rightVal.first), max(leftVal.second, rightVal.second)};
}
pair<int, int> find(int start, int end, int node, int left, int right)
{
    if (start > right || end < left)
        return {1000000001, 0};
    if (start >= left && end <= right)
        return tree[node];
    int mid = (start + end) >> 1;
    pair<int, int> leftVal, rightVal;
    leftVal = find(start, mid, node << 1, left, right);
    rightVal = find(mid + 1, end, (node << 1) + 1, left, right);
    return {min(leftVal.first, rightVal.first), max(leftVal.second, rightVal.second)};
}
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0);
    int N, M;
    cin >> N >> M;
    tree = vector<pair<int, int>>((N << 2));
    numV.push_back(0);
    for (int i = 0; i < N; ++i)
    {
        int num;
        cin >> num;
        numV.push_back(num);
    }
    init(1, N, 1);
    for (int i = 0; i < M; ++i)
    {
        int l, r;
        cin >> l >> r;
        auto cur = find(1, N, 1, l, r);
        cout << cur.first << " " << cur.second << "\n";
    }
}

풀이

지난 문제에서 세그먼트 트리 문제를 풀고 나니 더 풀어보고 싶었다. 그래서 찾아봤더니 이런 문제가 있었다.
이번 문제는 구간 합이 아닌 최대, 최소를 구하는 것이다. 그렇기에 각 구간에서의 최대, 최소를 트리로 저장해 주고 확인해 주는 방식을 취하면 됐다.

처음에는 최소, 최대를 나눠서 구해주는 방식으로 했는데 찾아보니 굳이 나누지 않더라도 해결할 수 있는 것을 알게 됐다. 그래서 수정해주었다.