2357번: 최소값과 최대값

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


$O((n+m)\lg n)$

sparse table을 이용한다.

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m;
struct st {
    int l, h;
    st operator+(st i) const {
        return{ min(l,i.l),max(h,i.h) };
    }
}dp[100001][17];
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        dp[i][0] = { x,x };
        for (int j = 1; 1 << j <= i; j++) dp[i][j] = dp[i][j - 1] + dp[i - (1 << j - 1)][j - 1];
    }
    for (int i = 0, x, y; i < m; i++) {
        scanf("%d %d", &x, &y);
        st r = { (int)1e9,0 };
        for (int i = 16; x <= y; i--) if (1 << i <= y - x + 1) r = r + dp[y][i], y -= 1 << i;
        printf("%d %d\n", r.l, r.h);
    }
    return 0;
}