10868번: 최소값

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

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1e5, LGN = 16;
int n, m, dp[MAX_N + 1][LGN + 1];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &dp[i][0]);
    for (int i = 1; i <= LGN; i++)
        for (int j = 1 << i; j <= n; j++)
            dp[j][i] = min(dp[j][i - 1], dp[j - (1 << i - 1)][i - 1]);
    for (int i = 0; i < m; i++) {
        int a, b, res = 0x7fffffff;
        scanf("%d %d", &a, &b);
        for (int j = LGN; j >= 0; j--)
            if (1 << j <= b - a + 1)
                res = min(res, dp[b][j]), b -= 1 << j;
        printf("%d\n", res);
    }
    return 0;
}