최소값

Tree, RMQ(rmq)


출처: BOJ최소값

SOL)
rmq


[-] Collapse

#include<stdio.h>
#include<algorithm>
using namespace std;

const int MAX = (1 << 30);

int rmq[4 * 100001];
int h = 1;
int main(){
    //freopen("input.txt", "r", stdin);
    int n, m; scanf("%d%d", &n, &m);
    //초기화
    for (int i = 0; i < 4 * 100001; i++) rmq[i] = MAX;
    while (h <= n) h <<= 1;
    for (int i = 0; i < n; i++) scanf("%d", &rmq[h + i]);
    for (int i = h - 1; i >= 1; i--) rmq[i] = min(rmq[i * 2], rmq[i * 2 + 1]);

    for (int i = 0; i < m; i++){
        int l, r; scanf("%d %d", &l, &r);
        l += h - 1; r += h - 1;
        int ans = MAX;
        while (l <= r){
            if (l & 1) ans = min(ans, rmq[l]);
            if (!(r & 1)) ans = min(ans, rmq[r]);
            l = (l + 1) >> 1;
            r = (r - 1) >> 1;
        }
        printf("%d\n", ans);
    }
    return 0;
}