백준 2357(최솟값과 최댓값)

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

2357번: 최솟값과 최댓값

전형적인 세그먼트 트리 개념 문제

웃기게도 알고리즘 시작할 때 공부한 개념이었는데 묻어뒀다가 까먹어서 다시 공부

 

세그는 최대 N*4의 배열 크기가 필요 

N개의 원소들이 주어지면 바텀업이 훨씬 편하다. 

 

요정도? 그리고 최댓값 구할 때나 최솟값 구할 때 빈 공간 잘 찾아주기 

그니깐 0으로 초기화 된 공간이 0이어도 괜찮은지 만약 최솟값을 찾는 거라면 0이 무조건 최솟값이 될 수 있으니 그런거 주의하자 

 

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
const int MAX = 100'005;
const int INF = 1e9;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

ll segment1[MAX * 4];
ll segment2[MAX * 4];
int sz;
int rs;

ll query1(int a, int b, int ia, int ib, int idx) {
    if (b < ia || ib < a)return 0;
    if (a <= ia && ib <= b)return segment1[idx];
    int mid = (ia + ib) / 2;
    return max(query1(a, b, ia, mid, idx * 2), query1(a, b, mid + 1, ib, idx * 2 + 1));
}

ll query2(int a, int b, int ia, int ib, int idx) {
    if (b < ia || ib < a)return LINF;
    if (a <= ia && ib <= b)return segment2[idx];
    int mid = (ia + ib) / 2;
    return min(query2(a, b, ia, mid, idx * 2), query2(a, b, mid + 1, ib, idx * 2 + 1));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    sz = 1 << 30;
    while (sz > N * 2) {
        sz /= 2;
    }
    rs = sz * 2;
    for (int i = 0; i < N; i++) {
        ll a;
        cin >> a;
        segment1[sz] = a;
        segment2[sz] = a;
        sz++;
    }
    for (int i = rs / 2 - 1; i >= 1; i--) {
        segment1[i] = max(segment1[i * 2], segment1[i * 2 + 1]);
        segment2[i] = min(segment2[i * 2], segment2[i * 2 + 1]);
    }

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        cout << query2(a, b, 1, rs/2-1, 1) << " " << query1(a, b, 1, rs/2-1, 1) << '\n';
    }
}