6213번: Balanced Lineup

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


$O(n+q\lg n)$

토너먼트 트리를 이용해 RMQ 문제를 푼다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 50000;
int n, q, u[MXN * 2], d[MXN * 2];
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", u + i + n);
        d[i + n] = u[i + n];
    }
    for (int i = n; --i;) {
        u[i] = max(u[i * 2], u[i * 2 + 1]);
        d[i] = min(d[i * 2], d[i * 2 + 1]);
    }
    while (q--) {
        int l, r, mini = 1e9, maxi = 0;
        scanf("%d%d", &l, &r);
        l += n - 1;
        r += n - 1;
        while (l <= r) {
            maxi = max({ maxi,u[l],u[r] });
            mini = min({ mini,d[l],d[r] });
            l = l + 1 >> 1;
            r = r - 1 >> 1;
        }
        printf("%d\n", maxi - mini);
    }
    return 0;
}