题意简述
给定一个有 $n$ 个数的数组，求从第一个数字开始，向后每 $k$ 个数字的最大值。
题目分析
看到没有人用 ST 表做那我就来发一个吧。
这道题可以用 ST 表做。它可以在经过 $O(N \log N)$ 的预处理后，以 $O(1)$ 的时间在线回答下标在 $l$ 到 $r$ 之间的数的最大值是几。
在代码中，$\mathit{f}_{i,j}$ 表示下标在 $i$ 到 $i+2^j-1$ 中的数的最大值。
Code
#include<bits/stdc++.h>
using namespace std;
int n,m,a[100001],f[100001][50],k;
int main(){
cin>>n;
memset(f,0x3f,sizeof(f));
for(int i=1;i<=n;i++){
cin>>a[i];
f[i][0]=a[i];
}
cin>>k;
for(int j=1;j<=20;j++){
for(int i=1;i<=n-(1<<j)+1;i++){
if(i+(1<<j)-1<=n) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}//以上为预处理f数组
for(int l=1;l<=n-k+1;l++){
int r=l+k-1;
int t=log2(r-l+1);
printf("%d ",max(f[l][t],f[r-(1<<t)+1][t]));
}//回答区间最大值
return 0;
}