SP10582 题解

题目链接

题意简述

给定一个有 \(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;
}