2357 최소값과 최대값

BOJ::2357 최소값과 최대값

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

세그먼트 트리를 활용해 풀었다.

pair를 이용해 두가지 정보를 저장할 트리 하나를 만들어서 해도 될거 같았지만

그냥 vector 두개를 만들어 최소값 트리, 최대값 트리 를 만들어 문제를 해결하였다.

#include <stdio.h>
#include <vector>
#include <math.h>
using namespace std;
#define INF 987987654321
#define MIN 1
#define MAX 2
 
typedef long long ll;
ll mm, MM;
int n, m;
 
ll min(ll a, ll b) {
    return (a < b) ? a : b;
}
ll max(ll a, ll b) {
    return (a > b) ? a : b;
}
 
//세그먼트 트리 초기화
ll init(vector<ll> &a, vector<ll> &tree, int node, int start, int end, int mode) {
    //리프노드인 경우
    if (start == end) {
        return tree[node] = a[start];
    }
    //리프노드가 아닌경우
    int mid = (start + end) >> 1;
    if (mode == MAX) {
        return tree[node] = max(init(a, tree, node << 1, start, mid, mode),
            init(a, tree, (node << 1) + 1, mid + 1, end, mode));
    }
    else {
        return tree[node] = min(init(a, tree, node << 1, start, mid, mode),
            init(a, tree, (node << 1) + 1, mid + 1, end, mode));
    }
 
}
 
//최대,최소값 구하기
void getResult(vector<ll> &minTree, vector<ll> &maxTree , int node, int start, int end, int left, int right) {
    //범위를 벗어나는경우
    if (left > end || right < start) return;
    // left와 right 에 범위가 포함되는경우
    if (left <= start && end <= right) {
        if (minTree[node] < mm) {
            mm = minTree[node];
        }
        if (maxTree[node] > MM) {
            MM = maxTree[node];
        }
        return;
    }
    //이저도저 아닌경우 --> 자식노드로 내려간다.
    int mid = (start + end) >> 1;
    getResult(minTree, maxTree, node << 1, start, mid, left, right);
    getResult(minTree, maxTree, (node << 1) + 1, mid + 1, end, left, right);
}
 
int main() {
    scanf("%d %d", &n, &m);
    int h = (int)ceil(log2(n));
    vector<ll> a(n);
    vector<ll> maxTree(1 << h + 1);
    vector<ll> minTree(1 << h + 1);
 
    for (int i = 0; i < n; i++) 
        scanf("%lld", &a[i]);
    // 세그먼트 트리 초기화
    init(a, maxTree, 1, 0, n - 1, MAX);
    init(a, minTree, 1, 0, n - 1, MIN);
 
    for (int i = 0; i < m; i++) {
        int left, right;
        mm = INF, MM = 0;
        scanf("%d %d", &left, &right);
        getResult(minTree, maxTree, 1, 0, n - 1, left - 1, right - 1);
        printf("%lld %lld\n", mm, MM);
    }
}