原题链接
题意：在线回答“数列A中下标在l~r之间的最大值与最小值的差是多少”
ST算法可以在O(NlogN)时间的预处理后，以O(1)的时间复杂度在线回答
ST打表工作，时间复杂度O(NlogN)
void ST_prework()
{
//初始化f数组
for(int i=1;i<=n;i++)
f[i][0]=a[i];
//t为最大长
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++)//枚举段长
for(int i=1;i<=n-(1<<j)+1;i++)//枚举起点,{1,2,[3,4,5,6]},段长为4，起点为6-4+1=3
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
在线查询[l,r]上的最大值的操作,时间复杂度为O(1)
int ST_query(int l,int r)
{
int k=log(r-l+1)/log(2)//使2的k次幂小于区间长度的前提下最大的k
return max(f[l][k],f[r-(1<<k)+1][k]);
}
简便起见，我们在代码中使用了cmath库的log函数，至于过不了poj报CE，就很无语(ˉ▽ˉ；)...
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int N=50005;
const int INF=0x3f3f3f3f;
int n,m;
int a[N];
int Fmax[N][20],Fmin[N][20];
void ST_prework()
{
for(int i=1;i<=n;i++)
{
Fmax[i][0]=a[i];
Fmin[i][0]=a[i];
}
int t=log(n)/log(2)+1;
for(int j=1;j<t;j++)//枚举区间长度种类
for(int i=1;i<=n-(1<<j)+1;i++)//枚举起点
{
Fmax[i][j]=max(Fmax[i][j-1],Fmax[i+(1<<(j-1))][j-1]);
Fmin[i][j]=min(Fmin[i][j-1],Fmin[i+(1<<(j-1))][j-1]);
}
}
int ST_query(int l,int r)
{
int k=log(r-l+1)/log(2);
return max(Fmax[l][k],Fmax[r-(1<<k)+1][k])-min(Fmin[l][k],Fmin[r-(1<<k)+1][k]);
}
int main()
{
cin>>n>>m;
memset(Fmax,INF,sizeof Fmin);
for(int i=1;i<=n;i++)
cin>>a[i];
ST_prework();
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
cout<<ST_query(l,r)<<endl;
}
return 0;
}
