poj 3264 Balanced Lineup

/*
给区间询问区间最大最小值的差
可以用st表
也可以用线段树
此处给出st表做法
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxn 500010
using namespace std;
int n,m,f[maxn][25],g[maxn][25];
int init()
{
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
void prepare()
{
    int i,j,k;
    for(j=1;j<=20;j++)
      for(i=1;i+(1<<(j-1))<=n;i++)
      {
          f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
          g[i][j]=min(g[i][j-1],g[i+(1<<(j-1))][j-1]);
      }
}
int find(int l,int r)
{
    int k=log(r-l+1)/log(2);
    int maxx=max(f[l][k],f[r-(1<<k)+1][k]);
    int minn=min(g[l][k],g[r-(1<<k)+1][k]);
    return maxx-minn;
}
int main()
{
    int i,j,k;
    n=init(),m=init();
    for(i=1;i<=n;i++)
    {
        int x;
        x=init();
        f[i][0]=x;
        g[i][0]=x;
    }
    prepare();
    for(i=1;i<=m;i++)
    {
        int x,y;
        x=init();
        y=init();
        if(x>y)swap(x,y);
        printf("%d
",find(x,y));
    }
    return 0;
}