ST算法

原题链接

题意：在线回答“数列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;
}