[BOJ-10868]최소값

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

[문제요약]

수가 주어지고, 주어진 수의 구간에서 최소값을 쿼리마다 출력한다.

[접근방법]

세그먼트 트리로 풀이할 수 있다. 

구간이 주어질 때마다 비교를 하게 되면 구간의 크기 N 이고, 쿼리의 수가 M 이면

O(NM) 연산을 해야한다. 

문제에서 최대 N = 100,000 , M = 100,000 이므로 시간초과를 받게되므로 세그트리로 풀이해야만 한다.

[C++11 source Code]

#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
 
typedef vector<long long> vll;
typedef long long ll;
const ll INF = 9876543211;
vll seg;
vll arr;
 
ll mn2(ll a, ll b) {
    return (a > b) ? b : a;
}
 
ll init(int node, int start, int end) {
    if (start == end) {
        return seg[node] = arr[start];
    }
    return seg[node] = mn2(init(node * 2, start, (start + end) / 2), init(node * 2 + 1, (start + end) / 2 + 1, end));
}
 
ll query(int node, int start, int end, int left, int right) {
    if (end < left || right < start) return INF;
    if (left <= start && end <= right) return seg[node];
 
    return mn2(query(2 * node, start, (start + end) / 2, left, right),
        query(2 * node + 1, (start + end) / 2 + 1, end, left, right));
}
 
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
 
    // tree create
    int h = ceil(log2(n));
    //printf("%d", h);
    seg = vll(1 << (h+2), 0);
    arr = vll(n, 0);
 
    for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);
 
    init(1, 0, n - 1);
 
    int a, b;
    for (int i = 0; i < q; i++) {
        scanf("%d%d", &a, &b);
        ll res = query(1, 0, n - 1, a - 1, b - 1);
        printf("%lld\n", res);
    }
 
    return 0;
}