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

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

2357번: 최솟값과 최댓값

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

long* tree_min;
long* tree_max;

void init(int S){
    for (int i=S-1; i>0; i--){
        tree_min[i]=min(tree_min[i*2], tree_min[i*2+1]);
        tree_max[i]=max(tree_max[i*2], tree_max[i*2+1]);
    }
}

long query_min(int left, int right, int node, int queryLeft, int queryRight){
    if (queryLeft<=left && right<=queryRight){
        return tree_min[node];
    }
    else if (right<queryLeft || queryRight<left){
        return MAX;
    }
    else{
        int mid=(left+right)/2;
        return min(query_min(left, mid, node*2, queryLeft, queryRight), query_min(mid+1, right, node*2+1, queryLeft, queryRight));
    }
}

long query_max(int left, int right, int node, int queryLeft, int queryRight){
    if (queryLeft<=left && right<=queryRight){
        return tree_max[node];
    }
    else if (right<queryLeft || queryRight<left){
        return 0;
    }
    else{
        int mid=(left+right)/2;
        return max(query_max(left, mid, node*2, queryLeft, queryRight), query_max(mid+1, right, node*2+1, queryLeft, queryRight));
    }
}


int main(){
    int N, M, x;
    int a,b;
    int S=1;
    vector<long> min_ans;
    vector<long> max_ans;
    cin>>N>>M;
    while (S<N){
        S*=2;
    }
    tree_min=new long[S*2];
    tree_max=new long[S*2];
    for (int i=S; i<S+N; i++){
        cin>>x;
        tree_min[i]=x;
        tree_max[i]=x;
    }
    for (int i=S+N; i<S*2; i++){
        tree_min[i]=MAX;
        tree_max[i]=0;
    }
    init(S);
    for (int i=0; i<M; i++){
        cin>>a>>b;
        min_ans.push_back(query_min(1,S,1,a,b));
        max_ans.push_back(query_max(1,S,1,a,b));
    }
    for (int i=0; i<M; i++){
        cout<<min_ans[i]<<" "<<max_ans[i]<<"\n";
    }
    delete [] tree_min;
    delete [] tree_max;
    return 0;
}

직관적인 Indexed Tree 문제.

mintree, maxtree를 따로 만들어줘서 이를 min, max 결과값을 각 노드에 넣고 query 연산을 해준다.

여기서 유의할점은 mintree는 범위 밖에 있는 노드일때는 MAX(여기서는 10만+1) 값을 반환하고 maxtree는 MIN값(여기서는 0) 을 반환해야 된다는 것이다.

두개로 각각 쪼개서 각 함수 리턴값에 대한 min, max를 구해주면 답이 나온다.