洛谷_3865 ST表
题意 给出一个序列，求某一个区间的最大值。(RMQ)
思路 【洛谷_3865 ST表】ST算法，设 f[i][j]f [ i ] [ j ] 表示从序列的第 ii 个位置开始 aja j 个数的最大值，我们可以得到公式 f[i][j]=max(f[i][j?1],f[i+2j?1][j?1])f [ i ] [ j ] = m a x ( f [ i ] [ j ? 1 ] , f [ i + 2 j ? 1 ] [ j ? 1 ] ) ,相当于把一个从 ii 到 2j2 j 的区间分成了两个长度为 2j?12 j ? 1 的区间。当我们查询最大值的时候，我们可以算出一个 kk ,就是让 2k<2 k < 这个区间长度时， kk 的最大值，那么我们查询的区间 (l,r)( l , r ) 的答案就为 max(f[l][k],f[r?2k+1][k])m a x ( f [ l ] [ k ] , f [ r ? 2 k + 1 ] [ k ] ) ,这两段刚好覆盖了这个区间，所以答案是准确的。
代码
#include
#include
#include
using namespace std;
int n,m,x,y,f[100001][22];
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;
i<=n;
i++)scanf("%d",&f[i][0]);
//初始化，因为从第i个数开始长度为1的区间的最大值就是它本身
for(int j=1;
j<=20;
j++)
for(int i=1;
i+(1< 推荐阅读
- 急于表达——往往欲速则不达
- 关于QueryWrapper|关于QueryWrapper,实现MybatisPlus多表关联查询方式
- mybatisplus如何在xml的连表查询中使用queryWrapper
- leetcode|leetcode 92. 反转链表 II
- 下雪了，飞去你的城市拥抱你|下雪了，飞去你的城市拥抱你 | 有个直男向我表白了
- 2019女表什么牌子好（如何挑选女士手表？）
- Python爬虫|Python爬虫 --- 1.4 正则表达式（re库）
- 佳琪（三十一）
- 霍兰德职业代码对照表
- 戏曲表演对幼儿的好处。