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

Segment tree를 활용했던 구간합 문제를 활용하는 방법을 알수 있다.

문제

문제 풀이

이번 문제는 segment tree의 기본였던 구간 합 구하기 문제에서 조금 활용하여서 최솟값과 최댓값을 구하는 문제이다. 만약 Segment tree에 대해서 잘 모르겠다면 아래 링크의 문제를 먼저 풀어보거나 풀이과정을 보고 오는 것을 추천한다.

백준 구간합 구하기 2042: https://koreaygj.github.io/algorithm/bj2042/

구간합은 Segment tree가 하나로 충분했지만, 이문제의 경우 최대값과 최솟값을 모두 구하기를 원하고 있기 떄문에 2개의 Segment tree를 사용했다. 그리고 구간합을 구할 필요없이, 구간의 최댓값, 최솟값을 구하는 것이기 때문에 재귀를 통해 더할 필요없이 min, max를 활용했다.

마지막으로 출력시에는 각각의 트리에서 구하고자 하는 구간에 해당하는 최댓값, 최솟값의 구간을 찾는 방식으로 출력했다.

---

전체코드 자세히 보기

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> max_tree(100005 * 4, 0);
vector<int> min_tree(100005 * 4, 0);
vector<int> arr(1000005, 0);
int init_max(int start, int end, int node)
{
    if(start == end)
        return max_tree[node] = arr[start];
    int mid = (start + end) / 2;
    return max_tree[node] = max(init_max(start, mid, node * 2) , init_max(mid + 1, end, node * 2 + 1));
}
int init_min(int start, int end, int node)
{
    if(start == end)
        return min_tree[node] = arr[start];
    int mid = (start + end) / 2;
    return min_tree[node] = min(init_min(start, mid, node * 2) , init_min(mid + 1, end, node * 2 + 1));
}
int find_max(int start, int end, int node, int left, int right)
{
    if(left > end || right < start)
        return 0;
    if(left <= start && end <= right)
        return max_tree[node];
    int mid = (start + end) / 2;
    return max(find_max(start, mid, node * 2, left, right), find_max(mid + 1, end, node * 2 + 1, left, right));
}
int find_min(int start, int end, int node, int left, int right)
{
    if(left > end || right < start)
        return 1000000005;
    if(left <= start && end <= right)
        return min_tree[node];
    int mid = (start + end) / 2;
    return min(find_min(start, mid, node * 2, left, right), find_min(mid + 1, end, node * 2 + 1, left, right));
}
int main(void){
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);
    int n, m;
    vector<pair<int, int>> input;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    init_max(1, n, 1);
    init_min(1, n, 1);
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        input.push_back({a, b});
    }
    for(int i = 0; i < m; i++)
    {
        cout << find_min(1, n, 1, input[i].first, input[i].second) << " " << find_max(1, n, 1, input[i].first, input[i].second) << "\n";
    }
}

---

문제 결과

문제 출처 https://www.acmicpc.net/problem/2357