[ BOJ 백준 2357번 - 최솟값과 최댓값 ] 해설 및 코드

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

목적

백준 2042 - 구간 합 구하기에 이어서 세그먼트 트리를 구현하자.

 

접근법

1. 세그먼트 트리 구현 예제이다. (위 게시물 참고할 것)

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<=r;++i)
#define fr(i,l,r) for(int i=l;i>=r;--i)
using namespace std;
typedef long long ll;
 
const int MX=1e9;
int n,m,offset,s[1<<19][2];
 
void query(){
    int a,b;cin>>a>>b;
    int mn=MX,mx=0;
    a+=offset;b+=offset;
    while(a<=b){
        if(a&1)mn=min(mn,s[a][0]),mx=max(mx,s[a++][1]);
        if(!(b&1))mn=min(mn,s[b][0]),mx=max(mx,s[b--][1]);
        a>>=1;b>>=1;
    }
    cout<<mn<<' '<<mx<<'\n';
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    
    offset=1;
    while(offset<n)offset<<=1;
    --offset;
    
    f(i,1,n)cin>>s[i+offset][0],s[i+offset][1]=s[i+offset][0];
    f(i,n+1,offset+1)s[i+offset][0]=MX,s[i+offset][1]=0;
    fr(i,offset,1){
        s[i][0]=min(s[i<<1][0],s[(i<<1)|1][0]);
        s[i][1]=max(s[i<<1][1],s[(i<<1)|1][1]);
    }
    
    while(m--)query();
    
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.