ST表

题目传送门

解题思路

这题就是ST表
我们设f[i][j]表示以i为左端点，长度为2^j的区间的最小值（最大值等）。 以最小值为例，显然可以有递推式
f [ i ] [ j ] = a [ i ] ( j = 0 ) f[i][j]=a[i] (j=0) f[i][j]=a[i](j=0) f [ i ] [ j ] = m ( f [ i ] [ j − 1 ] , f [ i + 2 ( j − 1 ) ] [ j − 1 ] ) ( j > 0 ) f[i][j]=m(f[i][j-1],f[i+2^(j-1)][j-1]) (j>0) f[i][j]=m(f[i][j−1],f[i+2(j−1)][j−1])(j>0) 建出来的f数组即为一个ST表

st表

AC代码

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,l,r,f[1000005][20]; 
int main()
{
   
    scanf("%d%d",&n,&m); 
    for(int i=1;i<=n;i++)//输入
       scanf("%d",&f[i][0]);
    for(int j=1;j<=log2(n);j++)//st表
     for(int i=1;i+(1<<j)-1<=n;i++)
      f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
    for(int i=1;i<=m;i++)
    {
   
     	scanf("%d%d",&l,&r);//输入
     	int k=log2(r-l+1);
     	printf("%d\n",max(f[l][k],f[r-(1<<k)+1][k]));//输出
    }
    return 0;
}

谢谢