poj 3264 RMQ

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn=5e4+9;
int maxrmq[maxn][20],minrmq[maxn][20],a[maxn];
int n,q;
void getrmq()
{
    for(int i=1;i<=n;i++)
    minrmq[i][0]=maxrmq[i][0]=a[i];
    for(int i=1;(1<<i)<=n;i++)
    for(int j=1;j+(1<<i)-1<=n;j++)
    {
        maxrmq[j][i]=max(maxrmq[j][i-1],maxrmq[j+(1<<i-1)][i-1]);
        minrmq[j][i]=min(minrmq[j][i-1],minrmq[j+(1<<i-1)][i-1]);
    }

}

int askrmq(int t,int s)
{
    int k=log(s-t+1)/log(2);
    int mmax=max(maxrmq[t][k],maxrmq[s-(1<<k)+1][k]);
    int mmin=min(minrmq[t][k],minrmq[s-(1<<k)+1][k]);
    return mmax-mmin;
}

int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d %d",&n,&q)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        getrmq();
        for(int i=1,t,s;i<=q;i++)
        {
            scanf("%d %d",&t,&s);
            printf("%d\n",askrmq(t,s));
        }
    }
    return 0;
}