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

문제 링크: https://www.acmicpc.net/problem/2357

2357번: 최솟값과 최댓값

1. 주의할 점

- 세그먼트 트리에 대해 알고 있어야 한다(세그먼트 트리 ↔ 구간 합이라고 생각했던에서 벗어나게 해준 문제다)

 

2. 구현

- 모든 수들을 Arr[] 배열에 담는다

- 부모로 자식중에서 Max값을 지닐 maxTree[]와 Min값을 지닐 minTree[]를 생성한다. 이때, MinTree[]는 전부 MAX로 초기화하여 추후에 0만 나오지 않도록 한다

- Init() 함수를 통해 최대값을 구하려는 경우 최대값을, 최소값을 구하려는 경우 최소값을 반환한다

- findVal() 함수를 통해 각 구간에 해당하는 최대 or 최소값을 반환하도록 한다

 

#define MAX 1000000001
#include <iostream>
#include <cmath>
using namespace std;
long long *maxTree;
long long *minTree;
long long arr[100000];

int init(int node, int start, int end, bool maximum){
    if(start==end){
        if(maximum) return maxTree[node] = arr[start];
        else return minTree[node] = arr[start];
    }
    int mid = start + (end-start)/2;
    if(maximum) return maxTree[node] = max(init(2*node,start,mid,maximum), init(2*node+1,mid+1,end,maximum));
    return minTree[node] = min(init(2*node,start,mid,maximum), init(2*node+1,mid+1,end,maximum));
}

int findVal(int node, int start, int end, int left, int right, bool maximum){
    if(left>end || right < start){
        if(maximum) return -MAX;
        return MAX;
    }
    if(left<=start && end<=right){
        if(maximum) return maxTree[node];
        else return minTree[node];
    }
    int mid = start + (end-start)/2;
    if(maximum) return max(findVal(node*2,start,mid,left,right,maximum),findVal(node*2+1,mid+1,end,left,right,maximum));
    return min(findVal(node*2,start,mid,left,right,maximum),findVal(node*2+1,mid+1,end,left,right,maximum));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int num,height,query,big,small,a,b;
    cin>>num>>query;
    height = ceil(log2(num));
    minTree = new long long[1<<(height+1)];
    maxTree = new long long[1<<(height+1)];
    for(int i=0;i<(1<<(height+1));i++)
        minTree[i]=MAX;
    for(int i=0;i<num;i++)
        cin>>arr[i];
    init(1,0,num-1,true);
    init(1,0,num-1,false);
    
    for(int i=0;i<query;i++){
        cin>>a>>b;
        big = a>b ? a : b;
        small = a>b ? b : a;
        cout << findVal(1,0,num-1,small-1,big-1,false)<<" "<<findVal(1,0,num-1,small-1,big-1,true)<<'\n';
    }
    return 0;
}