[2357번] 최소값과 최대값

문제 출처 :

https://www.acmicpc.net/problem/2357

알고리즘 분석 :

문제 해결에 필요한 사항

1. 세그먼트 트리(Segment Tree) :: http://www.crocus.co.kr/648

2. Pair STL :: http://www.crocus.co.kr/597

세그먼트 트리를 pair로 두어 각 노드마다(각 구간마다) 최대, 최솟값을 가지게 하도록 한다.

각각의 init를 두고, 각각의 query를 둬서 문제를 해결한다.

    // 범위를 벗어나면 return 후 최솟값으로 될 수 없게 INT_MAX로 설정한다.

    if (left > end || right < start)

        return INT_MAX;

queryMin에서 INT_MAX로 리턴하는 이유는 범위와 관계없는 값이 return이 됐을 때 그것이 최솟값으로 지정되면 안되기 때문이다.

    // 범위를 벗어나면 return 후 최댓값으로 될 수 없게 -1로 설정한다.

    if (left > end || right < start)

        return -1;

queryMax에서도 마찬가지로 return이 됐을 때 그것이 최댓값으로 지정되면 안되기에 -1로 return 한다.

소스 코드 : 

#include <cstdio>
#include <iostream>
#include <math.h>
#include <vector>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
// first :: 최솟값 second :: 최댓값 저장
typedef pair<int, int> pii;
 
// 최솟값을 init으로 초기에 세팅한다.
int initF(vector<int> &arr, vector<pair<int, int>> &tree, int node, int start, int end)
{
    if (start == end)
        return tree[node].first = arr[start];
 
    int mid = (start + end) / 2;
 
    return tree[node].first = min(initF(arr, tree, node * 2, start, mid), initF(arr, tree, node * 2 + 1, mid + 1, end));
}
 
// 최댓값을 init으로 초기에 세팅한다.
int initS(vector<int> &arr, vector<pair<int, int>> &tree, int node, int start, int end)
{
    if (start == end)
        return tree[node].second = arr[start];
 
    int mid = (start + end) / 2;
 
    return tree[node].second = max(initS(arr, tree, node * 2, start, mid), initS(arr, tree, node * 2 + 1, mid + 1, end));
}
 
// 최솟값을 queryMin을 통해 찾아낸다.
int queryMin(vector<pair<int, int>> &tree, int node, int start, int end, int left, int right)
{
    // 범위를 벗어나면 return 후 최솟값으로 될 수 없게 INT_MAX로 설정한다.
    if (left > end || right < start)
        return INT_MAX;
 
    if (left <= start && end <= right)
        return tree[node].first;
 
    int mid = (start + end) / 2;
 
    return min(queryMin(tree, node * 2, start, mid, left, right), queryMin(tree, node * 2 + 1, mid + 1, end, left, right));
}
 
// 최댓값을 queryMax을 통해 찾아낸다.
int queryMax(vector<pair<int, int>> &tree, int node, int start, int end, int left, int right)
{
    // 범위를 벗어나면 return 후 최댓값으로 될 수 없게 -1로 설정한다.
    if (left > end || right < start)
        return -1;
 
    if (left <= start && end <= right)
        return tree[node].second;
 
    int mid = (start + end) / 2;
    
    return max(queryMax(tree, node * 2, start, mid, left, right), queryMax(tree, node * 2 + 1, mid + 1, end, left, right));
}
 
int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
 
    int h = (int)ceil(log2(n));
    int tree_size = (1 << (1 + h));
 
    vector<int> arr(n);
    vector<pair<int ,int>> tree(tree_size);
 
 
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);
 
    initF(arr, tree, 1, 0, n - 1);
    initS(arr, tree, 1, 0, n - 1);
    
    for (int i = 0; i < m; i++)
    {
        int left, right;
        scanf("%d %d", &left, &right);
 
        printf("%d %d\n", queryMin(tree, 1, 0, n - 1, left-1, right-1), queryMax(tree, 1, 0, n - 1, left-1, right-1));
    }
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>