boj 2357 - 최솟값과 최댓값

BOJ 2357 - 최솟값과 최댓값

 

목차

설명

code

 

 

이 문제는 segment tree를 변형하면 해결할 수 있는 문제입니다. 기존에 child의 부분 합을 저장했다면, 이 문제에서는 child의 최소값과 최대값을 저장하면 됩니다.

 

Segment tree에 대한 설명은 [세그먼트 트리(Segment tree)]에서 볼 수 있습니다.

---

설명

BOJ 2357의 예제를 그대로 그려보면 다음과 같은 segment tree를 그릴 수 있을 것입니다!

Maximum Segment Tree

Minimum Segment Tree

18 ~ 23, 25 ~ 32 node는 segment tree의 코드를 따라 구현하면 관련이 없는 leaf ndoe입니다.

---

Code

1. 코드의 깔끔함을 위하여 같은 class로 구현하되, function pointer를 넘겨주어 minimum segment tree인지, maximum segment tree인지 구분할 수 있도록 하였습니다.

 

2. 문제상에서 segment tree의 update는 요구하지 않으므로 작성할 필요가 없습니다.

 

※주의할 점

3. Minimum tree인지, Maximum tree인지에 따라 node의 초기값 value가 달라집니다. BOJ 2357에서는 input의 최대값이 1,000,000,000 이므로 Minimum tree의 초기 value를 해당 값 이상으로만 설정해주면 됩니다.

 

4. Search의 첫 줄을 보시면, search range를 벗어난 query의 경우 init_val을 return하게 두었습니다. 만약 minimum tree에서 단순히 return 0을 했다면, caller에서 어떤 임의의 양수와 0을 비교하게 되므로 항상 0을 return하게 되어 정상적인 값을 얻어올 수 없습니다. 따라서 minimum tree의 out of range query 역시 INTMAX value를 return하도록 해야합니다.

#include<stdio.h>
#define INTMAX 1000000001

int N, M;
int arr[100000];

int min(int a, int b){
        return a > b? b : a;
}
int max(int a, int b){
        return a > b? a : b;
}
class Tree{
        int node[400000];
        public:
        
        //node의 value들을 초기화, minimum tree의 경우 MAX value로 초기화 해야함을 유의
        Tree(int init_val){
                for(int i=0;i<N*4;i++){
                        node[i] = init_val;
                }
        }
        
        //입력받은 array value를 기반으로 segment tree를 구성
        int Init(int cur, int *arr, int left, int right, int (*func)(int,int)){
                if(left==right){
                        node[cur] = arr[left];
                        return node[cur];
                }
                int mid = (left+right)/2;
                return node[cur] = func(Init(cur*2,arr,left,mid,func), Init(cur*2+1,arr,mid+1,right,func));
        }
        
        //구간 검색 Query
        int Search(int cur, int left, int right, int start, int end, int (*func)(int,int), int init_val){
                if(left > end || right < start) return init_val;
                if(start>=left && end <= right){
                        return node[cur];
                }
                int mid = (start+end)/2;
                return func(Search(cur*2, left, right, start, mid, func, init_val), Search(cur*2+1, left, right, mid+1, end, func, init_val));
        }
};

int main(){
        scanf("%d %d",&N,&M);
        for(int i=0;i<N;i++){
                scanf("%d",&arr[i]);
        }
        Tree *t_max = new Tree(0);
        Tree *t_min = new Tree(INTMAX);
        
        t_max->Init(1,arr,0,N-1, max);
        t_min->Init(1,arr,0,N-1, min);

        int a,b;
        for(int i=0; i<M;i++){
                scanf("%d %d",&a,&b);
                printf("%d %d\n",t_min->Search(1,a-1,b-1,0,N-1,min,INTMAX), t_max->Search(1,a-1,b-1,0,N-1,max,0));
        }
}