최솟값과 최댓값 - 2357

//2357 - 최솟값과 최댓값
 
#include <iostream>
#include <vector>
using namespace std;
 
#define INF 1000000001
 
int N, M;
int arr[100001];
 
struct SegmentTree
{
    int n;
    vector<int> mintree;
    vector<int> maxtree;
 
    SegmentTree(int n) : n(n), mintree(n*4+1), maxtree(n*4+1)
    {
        mininit(1, n, 1);
        maxinit(1, n, 1);
    }
 
    int mininit(int left, int right, int node)
    {
        if(left == right) return mintree[node] = arr[left];
        int mid = (left + right)/2;
        return mintree[node] = min(mininit(left, mid, node*2), mininit(mid+1, right, node*2+1));
    }
 
    int maxinit(int left, int right, int node)
    {
        if(left == right) return maxtree[node] = arr[left];
        int mid = (left + right)/2;
        return maxtree[node] = max(maxinit(left, mid, node*2), maxinit(mid+1, right, node*2+1));
    }
 
    int queryMin(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if(nodeRight < left || right < nodeLeft) return INF;
        if(left <= nodeLeft && nodeRight <= right)
            return mintree[node];
        
        int mid = (nodeLeft + nodeRight) / 2;
        return min(queryMin(left, right, nodeLeft, mid, node*2), 
                   queryMin(left, right, mid+1, nodeRight, node*2+1));
    }
 
    int queryMax(int left, int right, int nodeLeft, int nodeRight, int node)
    {
        if(nodeRight < left || right < nodeLeft) return 0;
        if(left <= nodeLeft && nodeRight <= right)
            return maxtree[node];
        
        int mid = (nodeLeft + nodeRight) / 2;
        return max(queryMax(left, right, nodeLeft, mid, node*2), 
                   queryMax(left, right, mid+1, nodeRight, node*2+1));
    }
 
    int queryMin(int left, int right)
    {   
        return queryMin(left, right, 1, n, 1);
    }
 
    int queryMax(int left, int right)
    {
        return queryMax(left, right, 1, n, 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> M;
    for(int i = 1; i<=N; ++i)
        cin >> arr[i];
    SegmentTree st(N);
    int x, y;
    for(int i = 0; i<M; ++i)
    {
        cin >> x >> y;
        cout << st.queryMin(x,y) << " " << st.queryMax(x, y) << "\n";
    }
}

 

 

 

 

 

 

 

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

2357번: 최솟값과 최댓값

 

 

 

 

 

 

 

최솟값과 최댓값

세그먼트 트리를 이용해 구간의 최소값과 최대값을 빠르게 구할수 있습니다.