关于模板ST表
  • 板块灌水区
  • 楼主Speccial
  • 当前回复18
  • 已保存回复18
  • 发布时间2021/7/29 09:58
  • 上次更新2023/11/4 12:47:37
查看原帖
关于模板ST表
361840
Speccial楼主2021/7/29 09:58

模板ST表,84分,wa#4和wa#11

不知道为什么这两个点没有过,求大神请教

代码如下

#include<cstdio>
#include<algorithm>

using namespace std;

int n,m,z[100100],f[100100][20],x[100100];

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&z[i]);
		f[i][0]=z[i];
	}
	for (int j=0;(1<<j) <= n;j++)
		for (int i=(1<<j); i < (1<<(j+1)); i++)
			x[i] = j;
	for(int j=1;(1<<j)<=n;j++)
	  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++)
	{
		int l,r;
		scanf("%d%d",&l,&r);
		int j=x[r-l+1];
		printf("%d\n",max(f[l][j],f[r-(1<<j)+1][j]));
	}
	return 0;
}
2021/7/29 09:58
加载中...