(SPOJ) RPLN - Negative Score [Sparse-Table]

http://www.spoj.com/problems/RPLN/

implement with sparse table

<O(n lg n), O(1)>

//use sparse table
#include <iostream>
#include <stdio.h>
using namespace std;

const int MAX_N = 1e5 +6;
const int MAX_P = 18;

int a[MAX_N];
int st[MAX_P][MAX_N];
int lg2[MAX_N];
int pow2[MAX_P];

int main () {
    pow2[0]=1;
    for (int i=1;MAX_P>i;i++) {
        pow2[i] = pow2[i-1]*2;
    }
    lg2[1] = 0;
    int id=1;
    for (int i=2;MAX_N>i;i++) {
        if (i==pow2[id]) {
            lg2[i] = lg2[i-1]+1;
            id++;
        }
        else {
            lg2[i] = lg2[i-1];
        }
    }
    int T;
    scanf("%d",&T);
    int cases=0;
    while (T--) {
        int n,q;
        scanf("%d %d",&n,&q);
        for (int i=1;n>=i;i++) {
            scanf("%d",&a[i]);
            st[0][i] = a[i];
        }
        for (int i=1;MAX_P>i;i++) {
            for (int j=1;n>=j;j++) {
                int r=j+pow2[i-1];
                if (r>n) r=n;
                st[i][j] = min(st[i-1][j],st[i-1][r]);
            }
        }
        printf("Scenario #%d:\n",++cases);
        while (q--) {
            int l,r;
            scanf("%d %d",&l,&r);
            int dis=(r-l+1);
            printf("%d\n",min(st[lg2[dis]][l],st[lg2[dis]][r-pow2[lg2[dis]]+1]));
        }
    }
}