POJ3264 Balanced Lineup

http://poj.org/problem?id=3264
クラシックRMQタイトル.RMQ問題は,与えられた区間における最値を求める問題である.素朴アルゴリズムはO(n)であり,線分ツリーを用いてアルゴリズムをO(logn)(線分ツリーに線分の最値を保存する)に最適化できる.
ただし、クエリーのみではRMQアルゴリズムが最適です.O(nlogn)の前処理後にO(1)のクエリー効率を実現できます.線分ツリーの主な違いは区間を修正できることで、RMQはできません.以下、Sparse Tableアルゴリズムを前処理とクエリーの2つの部分に分けて説明します.倍増思想を用いました.前処理:最大値を求める例として、d[i,j]を[i,i+2^j-1]として表しますこの区間内の最大値は、[a,b]区間の最大値を尋ねると、答えはmax(d[a,k],d[b-2^k+1,k])であり、kは2^k<=b-a+1(すなわち長さ)を満たす最大のk、すなわちk=[ln(b-a+1)/ln(2)]である.dの求め方は、動的に計画することができ、d[i,j]=max(d[i,j-1],d[i+2^(j-1),j-1])である.したがって、条件に合致するすべてのdを下から上へのアルゴリズムで繰り返すことができる(i,j)の値.
クエリー:クエリーの巧みな点は[m,n]を2つの部分が重なる区間に分けることです.そこで、[m,n]を2^kの長さの区間に分けることができます.[m,m+2^k-1],[n-2^k+1,n];
この問題のいくつかの注意点:1.繰返しに注意するときは長さ2^0から2^jで繰返し、jのループは外に置く;2.log関数を使うときは、中のパラメータはdouble;3.2を求めるpowerはよく使われる操作で、左シフト<<操作が非常に適切である;4.cin/coutはタイムアウトし、scanf/printfを使う.

#include <iostream>

#include <cmath>



using namespace std;

#define LEN 50005

#define LOG_LEN 20

#define MAX(a,b) (a>b?a:b)

#define MIN(a,b) (a<b?a:b)

#define ABS(a) (a<0?-a:a)

const int INF (1<<30);



int cow[LEN];

int fmin[LEN][LOG_LEN];

int fmax[LEN][LOG_LEN];

int Q;

int N;



void init()

{

    memset(cow, 0, sizeof(cow));

    memset(fmin, 0, sizeof(fmin));

    memset(fmax, 0, sizeof(fmax));



    scanf("%d%d", &N, &Q);

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

    {

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

    }

}



void build()

{

    // build the RMQ

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

    {

        fmin[i][0] = cow[i];

        fmax[i][0] = cow[i];

    }

    int size = int (log((double)(N + 1)) / log(2.0));

    

    for (int j = 1; j <= size; j++)

    {

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

        {

            fmin[i][j] = MIN(fmin[i][j - 1], fmin[i + (1 << (j - 1))][j-1]);

            fmax[i][j] = MAX(fmax[i][j - 1], fmax[i + (1 << (j - 1))][j-1]);

        }

    }

}



int query(int left, int right)

{

    int diff = right - left + 1;

    int k = (int) (log((double)diff) / log(2.0));

    int min = MIN(fmin[left][k], fmin[right - (1 << k) + 1][k]);

    int max = MAX(fmax[left][k], fmax[right - (1 << k) + 1][k]);

    return max - min;

}



int main()

{

    init(); 

    build();

    

    // query

    for (int i = 0; i < Q; i++)

    {

        int x, y;

		scanf("%d%d", &x, &y);     

        printf("%d
", query(x, y));  

    }

    return 0;

}