st表

求最大值

f ( i , j ) 是从 i 到 $i+2^j$ 的最大值，ennnnnnnnnnnnnn，

首先我们用倍增的思想

$$ f[j][i]=max(f[j][i-1],f[j+(o>>1)][i-1]) $$

因为当前区间可以分为前半段和后半段，那么当前区间的最大值就是两端最大值的 $max$


#define II int
#define R register
#define I 123456
using namespace std;

II f[I][30];
II n,q;

int ()
{
	scanf("%d%d",&n,&q);
	for(R II i=1;i<=n;i++) scanf("%d",&f[i][0]);

	for(R II i=1;(1<<i)<=n;i++)
	
	{
		R II o=1<<i;
		for(R II j=1;j<=n-o+1;j++)
		// 这里要j<=n-o+1；
			f[j][i]=max(f[j][i-1],f[j+(o>>1)][i-1]);
	}

	while (q--) {
		R II l,r,ans=-1e9;
		scanf("%d%d",&l,&r);
		R II o=log(r-l+1)/log(2);
		ans=max(f[l][o],f[r-(1<<o)+1][o]);
		printf("%dn",ans);
	}
	exit(0);
}

近期文章

近期评论

标签

热门

文章归档

分类目录

功能