POJ-3264 Balanced Lineup RMQ

두 개의 그룹을 직접 유지하면 됩니다. 매번 방문할 때마다 구간의 최소값과 최대값을 얻을 수 있습니다.
코드는 다음과 같습니다.

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;



int N, M, seq[50005], Min[50005][20], Max[50005][20];



void Minbuild()

{

    int LIM = (int)log2(double(N));

    for (int i = 1; i <= N; ++i) {

        Min[i][0] = seq[i]; 

    }

    for (int j = 1; j <= LIM; ++j) {

        for (int i = 1; i+(1<<j)-1 <= N; ++i) {

            Min[i][j] = min(Min[i][j-1], Min[i+(1<<j-1)][j-1]);

        }

    }

}



void Maxbuild()

{

    int LIM = (int)log2(double(N));

    for (int i = 1; i <= N; ++i) {

        Max[i][0] = seq[i];    

    }

    for (int j = 1; j <= LIM; ++j) {

        for (int i = 1; i+(1<<j)-1 <= N; ++i) {

            Max[i][j] = max(Max[i][j-1], Max[i+(1<<j-1)][j-1]);    

        }

    }

}



int Maxquery(int l, int r)

{

    int k = (int)log2(double(r-l+1));

    return max(Max[l][k], Max[r-(1<<k)+1][k]);

}



int Minquery(int l, int r)

{

    int k = (int)log2(double(r-l+1)); 

    return min(Min[l][k], Min[r-(1<<k)+1][k]);

}



int main()

{

    int l, r;

    while (scanf("%d %d", &N, &M) == 2) {

        for (int i = 1; i <= N; ++i) {

            scanf("%d", &seq[i]);    

        }

        Minbuild(), Maxbuild();

        for (int i = 1; i <= M; ++i) {

            scanf("%d %d", &l, &r); 

            printf("%d
", Maxquery(l, r) - Minquery(l, r));

        }

    }

    return 0;    

}