#题解##P2880 [USACO07JAN] Balanced Lineup G#

st算法

#include<bits/stdc++.h>
using namespace std;
int n,q,l,r;
int arr[50010]={0};
int dpmin[50010][21],dpmax[50010][22];
void stat()
{
    for(int i=1;i<=n;i++)//初始化区间长度为2的0次幂即1
    {
        dpmin[i][0]=arr[i];
        dpmax[i][0]=arr[i];
    }
    int p=log2(n);
    for(int k=1;k<=p;k++)
    {
        for(int s=1;s+(1<<k)<=n+1;s++)
        {
            dpmax[s][k]=max(dpmax[s][k-1],dpmax[s+(1<<(k-1))][k-1]);
            dpmin[s][k]=min(dpmin[s][k-1],dpmin[s+(1<<(k-1))][k-1]);
        }
    }
}
int stqu(int ll,int rr)
{
    int k=log2(rr-ll+1);
    int x=max(dpmax[ll][k],dpmax[rr-(1<<k)+1][k]);
    int y=min(dpmin[ll][k],dpmin[rr-(1<<k)+1][k]);
    return x-y;
}
int main()
{
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>arr[i];
    }
    stat();
    for(int i=0;i<q;i++)
    {
        cin>>l>>r;
        cout<<stqu(l,r)<<endl;
    }
> }