2357 최소값과 최대값

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

최소값과 최대값 각각에 대하여 세그먼트 트리를 만들어 준다.

#include <cstdio>
#include <algorithm>
using namespace std;
 
int n,m,a[100001],maxt[400000],mint[400000];
 
void max_init(int node,int start,int end)
{
    if(start==end)
        maxt[node]=a[start];
    else
    {
        max_init(node*2,start,(start+end)/2);
        max_init(node*2+1,(start+end)/2+1,end);
        maxt[node]=max(maxt[node*2],maxt[node*2+1]);
    }
}
 
void min_init(int node,int start,int end)
{
    if(start==end)
        mint[node]=a[start];
    else
    {
        min_init(node*2,start,(start+end)/2);
        min_init(node*2+1,(start+end)/2+1,end);
        mint[node]=min(mint[node*2],mint[node*2+1]);
    }
}
 
int max_query(int node,int start,int end,int i,int j)
{
    if(j<start || end<i) return -1;
    if(i<=start && end<=j) return maxt[node];
    int max1=max_query(node*2,start,(start+end)/2,i,j);
    int max2=max_query(node*2+1,(start+end)/2+1,end,i,j);
    if(max1==-1) return max2;
    else if(max2==-1) return max1;
    else return max(max1,max2);
}
 
int min_query(int node,int start,int end,int i,int j)
{
    if(j<start || end<i) return -1;
    if(i<=start && end<=j) return mint[node];
    int min1=min_query(node*2,start,(start+end)/2,i,j);
    int min2=min_query(node*2+1,(start+end)/2+1,end,i,j);
    if(min1==-1) return min2;
    else if(min2==-1) return min1;
    else return min(min1,min2);
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    max_init(1,1,n),min_init(1,1,n);
    while(m--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d %d\n",min_query(1,1,n,a,b),max_query(1,1,n,a,b));
    }
    return 0;
}