poj3264 倍增法（ST表）裸题

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 50010
int mx[maxn][20],mi[maxn][20],d[maxn];
void initmax(int n,int d[]){
    for(int i=1;i<=n;i++) mx[i][0]=d[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}           
int getmax(int L,int R){
    int k=0;
    while((1<<(k+1))<=R-L+1) k++;
    return max(mx[L][k],mx[R-(1<<k)+1][k]);
}               
void initmin(int n,int d[]){
    for(int i=1;i<=n;i++) mi[i][0]=d[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            mi[i][j]=min(mi[i][j-1],mi[i+(1<<(j-1))][j-1]);
}
int getmin(int L,int R){
    int k=0;
    while((1<<(k+1))<=R-L+1) k++;
    return min(mi[L][k],mi[R-(1<<k)+1][k]);
}
int main(){
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
        for(int i=1;i<=n;i++) scanf("%d",&d[i]);
        initmax(n,d);initmin(n,d);
        while(q--){
            int L,R;
            scanf("%d%d",&L,&R);
            printf("%d
",getmax(L,R)-getmin(L,R));
        }
    }
    return 0;
}