최솟값과 최댓값

문제 링크 이 문제는 이유를 모르겠는데 업데이트 쿼리를 요구하지 않는다. 곱셈 세그먼트 트리와 완전히 같은 구조로 구현이 가능하므로 업데이트 쿼리도 한번 구현 해보기를 추천한다.

풀이

곱셈 세그먼트 트리와 완전히 같은 구조다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
using ll = long long;
struct node {
    ll mn = (ll)9e18, mx = (ll)-9e18;
};
int n, m;
vector<ll> arr;
vector<node> seg;
// n : tree 기준 노드 번호
// s : 배열 구간 시작 인덱스
// e : 배열 구간 종료 종료 인덱스
node init(int n, int s, int e) {
    if (s == e) { // 시작 인덱스와 종료 인덱스가 같다면 리프 노드이므로 배열값 반환
        return seg[n] = { arr[s], arr[s] };
    }
    int mid = (s + e) / 2;
    node s1 = init(n * 2, s, mid); // 왼자식 탐색
    node s2 = init(n * 2 + 1, mid + 1, e); // 오른자식 탐색
    return seg[n] = { s1.mn < s2.mn ? s1.mn : s2.mn, s1.mx > s2.mx ? s1.mx : s2.mx }; // 양쪽 자식 최대 / 최소값 비교 후 더 나은 쪽 리턴
}
// n : tree 기준 노드 번호
// l : 합을 구하는 구간 시작 인덱스
// r : 합을 구하는 구간 종료 인덱스
// s : 배열 구간 시작 인덱스
// e : 배열 구간 종료 종료 인덱스 
node getmnmx(int n, int l, int r, int s, int e) {
    if (l <= s && e <= r) return seg[n]; // 구간을 완전히 포함하는 경우, 노드 값 반환
    if (r < s || e < l) return { (ll)9e18, (ll)-9e18 }; // 구간이 전혀 포함되지 않는 경우, 최대 최소 쓰레기값 반환 ( 9e18, -9e18 )
    int mid = (s + e) / 2;
    node s1 = getmnmx(n * 2, l, r, s, mid); // 왼자식 탐색 
    node s2 = getmnmx(n * 2 + 1, l, r, mid + 1, e); // 오른자식 탐색
    return { s1.mn < s2.mn ? s1.mn : s2.mn, s1.mx > s2.mx ? s1.mx : s2.mx }; // 양쪽 자식 최대 / 최소값 비교 후 더 나은 쪽 리턴
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m; arr = vector<ll>(n + 1); seg = vector<node>((int)pow(2, (int)ceil(log2(n)) + 1));
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }
    init(1, 1, n);
    for (int i = 1; i <= m; i++) {
        int s, e; cin >> s >> e;        
        node ret = getmnmx(1, s, e, 1, n);
        cout << ret.mn << " " << ret.mx << "\n";        
    }
    return 0;
}