2357 - 최솟값과 최댓값(C++)

문제

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이하의 값을 갖는다.

입력

첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가 주어진다. 다음 M개의 줄에는 a, b의 쌍이 주어진다.

출력

M개의 줄에 입력받은 순서대로 각 a, b에 대한 답을 최솟값, 최댓값 순서로 출력한다.

풀이

가장 기본적인 형태의 세그먼트 트리는 부분 합을 트리에 저장하는 방식이지만 이 문제에서는 부분수열의 최솟값과 최댓값을 트리에 저장하는 방식으로 해결하면 된다. 이를 구현하기 위해 최솟값을 저장하는 트리와 최댓값을 저장하는 트리 2개를 각각 구성하여 구현하였다. vector<int> minTree,maxTree

트리의 높이는 int h = ceil(log2(N)) 로 구한 후 각 트리의 사이즈는 int treeSize = (1 << (h+1)) 를 통해 계산 후 두 개의 트리 크기를 초기화한다. 이후 init() 함수를 통해 각 트리의 최소, 최대값을 넣고 search()함수를 사용하여 답을 출력한다.

여기서 search()함수의 반환형이 pair<int,int> 인 이유는 왼쪽 노드와 오른쪽 노드를 모두 호출하여 두 노드에서의 최소, 최대를 비교 후 값을 출력하기 위해서이다.

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define MAX 2e9
int arr[1000001];
vector<int> minTree,maxTree;
int N,M;
void input(){
    cin>>N>>M;
    for(int i=1;i<=N;i++){
        cin>>arr[i];
    }
}
void init(int start, int end, int node){
    if(start==end){
        minTree[node] = arr[start];
        maxTree[node] = arr[start];
        return;
    }
    int mid = (start+end)/2;
    init(start,mid,node*2);
    init(mid+1,end,node*2+1);
    minTree[node] = min(minTree[node*2],minTree[node*2+1]);
    maxTree[node] = max(maxTree[node*2],maxTree[node*2+1]);
}
pair<int,int> search(int start, int end, int node, int left, int right){
    if(left>end || right<start)
        return {MAX,0};
    if(left<=start && right>=end)
        return {minTree[node],maxTree[node]};
    pair<int,int> l,r;
    int mid = (start+end)/2;
    l = search(start,mid,node*2,left,right);
    r = search(mid+1,end,node*2+1,left,right);
    return {min(l.first,r.first),max(l.second,r.second)};

}
void solve(){
    int a,b;
    pair<int,int> ans;
    int h = ceil(log2(N));
    int treeSize = (1 << (h+1));
    minTree = vector<int>(treeSize);
    maxTree = vector<int>(treeSize);
    init(1,N,1);
    for(int i=0;i<M;i++){
        cin>>a>>b;
        ans = search(1,N,1,a,b);
        cout<<ans.first<<" "<<ans.second<<"\n";
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    input();
    solve();
    return 0;
}