10868. 최솟값

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

10868번: 최솟값

 

 

 

티어 : 골드1

 

세그먼트 트리로 풀었다.

15분 정도 걸린거 같다.

 

 

#include<stdio.h>
#include<algorithm>

using namespace std;
#define MAX 1000000000;

int arr[100005], seg[400005];

int n, m;

int init(int index, int left, int right){
    if(left == right) return seg[index] = arr[left];
    int mid = (left + right) / 2;
    return seg[index] = min( init(index*2, left, mid), init(index*2+1, mid+1, right) );
}

int find(int index, int left, int right, int a, int b){
    if(a <= left && right <= b) return seg[index];
    if(right < a || b < left) return MAX + 1;
    int mid = (left + right) / 2;
    return min( find(index*2, left, mid, a, b), find(index*2+1, mid+1, right, a, b) );
}

int main()
{
    scanf("%d %d", &n, &m);
    for(int i=1 ; i<=n ; i++) scanf("%d", &arr[i]);
    init(1, 1, n);

    for(int i=0 ; i<m ; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", find(1, 1, n, a, b));
    }
}