BOJ 2357 - 최솟값과 최댓값

문제 태그 : https://www.acmicpc.net/problem/2357

문제 소개 

N개의 숫자들이 주어지고 쿼리가 주어진다. 쿼리가 a,b가 주어지면 a번째 숫자부터 b번째 숫자 사이의 최솟값과 최댓값을 구해야 한다. 

문제 풀이

 지금은 N개의 숫자들이 바뀌지는 않지만, 아무튼 구간의 최댓값과 구간의 최솟값은 Segment Tree를 사용함으로써 한 번 구하는 데 $O(lgN)$에 구할 수 있음이 잘 알려져 있다.
 구간합을 구할 때 구하고자 하는 구간에 포함되어지지 않는 노드는 0을 반환한다. 항등원이기 때문이다. 같은 이유로 최솟값 세그트리에서는 항등원인 inf를 반환해야 하고, 최댓값연산에서는 항등원이 -inf이므로 구간이 포함되어지지 않으면 -inf를 반환해야 한다. 

코드

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int tree[maxn*4];
int tree2[maxn*4];
int arr[maxn];
int n,m;
long long init(int node, int start,int end)
{
    if(start==end) return tree[node]=arr[start];
    else return tree[node]=min( init(node*2,start,(start+end)/2),
                                init(node*2+1,(start+end)/2+1,end) );
}
 
long long init2(int node, int start,int end)
{
    if(start==end) return tree2[node]=arr[start];
    else return tree2[node]=max( init2(node*2,start,(start+end)/2),
                                 init2(node*2+1,(start+end)/2+1,end) );
}
 
long long mingap(int node,int st,int en, int l,int r)
{
    if(r<st || l>en ) return 1000000009;
    if(l<=st&&en<=r) return tree[node];
    return min ( mingap( node*2, st, (st+en)/2, l, r),
                 mingap( node*2+1, (st+en)/2+1, en,l,r) ) ;
}
 
long long maxgap(int node,int st,int en, int l,int r)
{
    if(r<st || l>en ) return 0;
    if(l<=st&&en<=r) return tree2[node];
    return max(maxgap( node*2, st, (st+en)/2, l, r),
               maxgap( node*2+1, (st+en)/2+1, en,l,r) ) ;
}
 
int main()
{
    int i,j,k;
    scanf("%d",&n);
    scanf("%d",&m);
    
    for(i=1;i<=n;i++)
        scanf("%d",&arr[i]);
    init(1,1,n);
    init2(1,1,n);
    while(m--)
    {
        int t2,t3;
        scanf("%d %d",&t2,&t3);
        printf("%lld %lld\n",mingap(1,1,n,t2,t3),maxgap(1,1,n,t2,t3));
    }
    return 0;    
}