2019.9.5 数列区间最大值

题目传送门

ST表板子 不解释

上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define int long long
using namespace std;
int n,m,dp[100050][55],a[100050];
void init()
{
    for(int i=1;i<=n;i++)dp[i][0]=a[i];
    for(int j=1;(1<<j)<=n;j++)
        for(int i=1;i+(1<<j)-1<=n;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
int maxnum(int l,int r)
{
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    init();
    int x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&x,&y);
        printf("%lld
",maxnum(x,y));
    }
    return 0;
}