백준 2357 최솟값과 최댓값 c++

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

2357번: 최솟값과 최댓값

 

2개의 세그먼트 트리를 만들면 풀 수 있는 문제였습니다

#include <iostream>
#include <math.h>
#define fastio() ios::sync_with_stdio(0),cin.tie(nullptr),cout.tie(nullptr);
using namespace std;
typedef long long ll;
ll n, m, from;
ll maxarr[10000000];
ll maximum(ll l, ll r, ll idx = 1, ll L = 1, ll R = from) {
    if (l > R or r < L) return -2000000000;
    else if (l <= L and r >= R) return maxarr[idx];
    ll m = (L + R) / 2;
    return max(maximum(l, r, idx * 2, L, m), maximum(l, r, idx * 2 + 1, m + 1, R));
}
ll minarr[10000000];
ll minimum(ll l, ll r, ll idx = 1, ll L = 1, ll R = from) {
    if (l > R or r < L) return 2000000000;
    else if (l <= L and r >= R) return minarr[idx];
    ll m = (L + R) / 2;
    return min(minimum(l, r, idx * 2, L, m), minimum(l, r, idx * 2 + 1, m + 1, R));
}
int main() {
    fastio();
    cin >> n >> m;
    from = ((n & (n - 1)) == 0) ? pow(2, (int)log2(n)) : pow(2, (int)log2(n) + 1);
    for (ll i = from; i < from + n; i++) {
        cin >> maxarr[i];
        minarr[i] = maxarr[i];
    }
    for (ll i = from - 1; i >= 1; --i) {
        maxarr[i] = max(maxarr[i * 2], maxarr[i * 2 + 1]);
        minarr[i] = min(minarr[i * 2], minarr[i * 2 + 1]);
    }
    for (ll i = 0; i < m; i++) {
        ll a, b;
        cin >> a >> b;
        cout << minimum(a, b) << " " << maximum(a, b) << "\n";
    }
}

 

풀이: 

https://wantchicken.tistory.com/46

세그먼트 트리의 개념 - c++