10868번 최솟값

 세그먼트 트리 기본 문제.

 

 2357번 문제를 풀었을때와 마찬가지로 'endl'을 사용해 출력하면 시간초과가 뜬다.

 

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>
#define MAX 100001
 
using namespace std;
 
int N, M;
 
int arr[MAX];
vector<int> answer;
 
int mininit(int start, int end, int node, int* mintree) {
    if (start == end) return mintree[node] = arr[start];
    int mid = (start + end) / 2;
    //재귀적으로 두 부분으로 나눈 뒤에 그 최솟값을 자기 자신으로 합니다.
    return mintree[node] = min(mininit(start, mid, node * 2, mintree),mininit(mid + 1, end, node * 2 + 1, mintree));
}
 
int minquery(int start, int end, int node, int left, int right,int* mintree) {
    //범위 밖에 있는 경우
    if (left > end || right < start) return INT_MAX;
    //범위 안에 있는 경우
    if (left <= start && end <= right) return mintree[node];
    //그렇지 않다면 두 부분으로 나누어 최솟값을 구하기
    int mid = (start + end) / 2;
    return min(minquery(start, mid, node * 2, left, right, mintree), minquery(mid + 1, end, node * 2 + 1, left, right, mintree));
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    int size = N * 4;
 
    int* mintree = new int[size];
 
    mininit(0, N - 1, 1, mintree);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        int minN = minquery(0, N-1,1, a-1, b-1, mintree);
        
        answer.push_back(minN);
    
    }
 
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i] << "\n";
    }
}