2357번 최솟값과 최댓값

 세그먼트 트리 문제.

 

 마지막 결과값을 보여주는 과정에서 "\n" 대신 endl을 사용하면 시간초과가 뜬다. 

(endl에는 새줄(개행)뿐만 아니라 출력 함수의 끝을 알림으로써 버퍼를 정리하는 기능이 있어 오래걸리는듯 싶다)

 

#include <iostream>
#include <algorithm>
#include <limits.h>
#include <vector>
#define MAX 100001
 
using namespace std;
 
int N, M;
 
typedef pair<int, int> pir;
int arr[MAX];
vector<pir> 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 maxinit(int start, int end, int node, int* maxtree) {
    if (start == end) return maxtree[node] = arr[start];
    int mid = (start + end) / 2;
    //재귀적으로 두 부분으로 나눈 뒤에 그 최솟값을 자기 자신으로 합니다.
    return maxtree[node] = max(maxinit(start, mid, node * 2, maxtree), maxinit(mid + 1, end, node * 2 + 1, maxtree));
}
 
int maxquery(int start, int end, int node, int left, int right, int* maxtree) {
    //범위 밖에 있는 경우
    if (left > end || right < start) return -1;
    //범위 안에 있는 경우
    if (left <= start && end <= right) return maxtree[node];
    //그렇지 않다면 두 부분으로 나누어 최솟값을 구하기
    int mid = (start + end) / 2;
    return max(maxquery(start, mid, node * 2, left, right, maxtree), maxquery(mid + 1, end, node * 2 + 1, left, right, maxtree));
}
 
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];
    int* maxtree = new int[size];
 
    mininit(0, N - 1, 1, mintree);
    maxinit(0, N - 1, 1, maxtree);
 
    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);
        int maxN = maxquery(0, N-1,1, a-1, b-1, maxtree);
 
        answer.push_back(pir(minN,maxN));
    
    }
 
    for (int i = 0; i < answer.size(); i++) {
        cout << answer[i].first << " " << answer[i].second << "\n";
    }
}