문제

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.

해설

단순히 특정 구간의 최솟값과 최댓값을 각각 배열에 저장한다면 메모리초과를 피할 수 없다.
따라서, 세그먼트 트리를 활용하여 최솟값,최댓값 트리를 만들어 준다.

접근방식 1 (dfs)

#include <bits/stdc++.h>
using namespace std;
const long long INF=1LL<<60;
long long n,m,arr[100001],maxTree[400004],minTree[400004];
long long maxInit(int s,int e,int x){
    if(s==e)return maxTree[x]=arr[s];
    int mid=(s+e)/2;
    return maxTree[x]=max(maxInit(s,mid,x*2),maxInit(mid+1,e,x*2+1));
}long long minInit(int s,int e,int x){
    if(s==e)return minTree[x]=arr[s];
    int mid=(s+e)/2;
    return minTree[x]=min(minInit(s,mid,x*2),minInit(mid+1,e,x*2+1));
}long long maxQuery(int s,int e,int l,int r,int x){
    if(l>e||r<s)return 0;
    if(l<=s&&e<=r)return maxTree[x];
    int mid=(s+e)/2;
    return max(maxQuery(s,mid,l,r,x*2),maxQuery(mid+1,e,l,r,x*2+1));
}long long minQuery(int s,int e,int l,int r,int x){
    if(l>e||r<s)return INF;
    if(l<=s&&e<=r)return minTree[x];
    int mid=(s+e)/2;
    return min(minQuery(s,mid,l,r,x*2),minQuery(mid+1,e,l,r,x*2+1));
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> arr[i];
    }maxInit(0,n-1,1);
    minInit(0,n-1,1);
    while(m--){
        int a,b;
        cin >> a >> b;a--;b--;
        cout << minQuery(0,n-1,a,b,1) << ' ' << maxQuery(0,n-1,a,b,1) << '\n';
    }
}