锐客网

  1. 首页 > it技术 > >

经典算法题|st算法

题目背景
这是一道ST表经典题——静态区间最大值
题目描述
给定一个长度为 N的数列，和 M 次询问，求出每一次询问的区间内数字的最大值。
输出格式：
输出包含 M M行，每行一个整数，依次表示每一次询问的结果。
【经典算法题|st算法】输入输出样例
输入样例#1：
8 8
9 3 1 7 5 6 0 8
1 6
1 5
2 7
2 6
1 8
4 8
3 7
1 8
输出样例#1：
9
9
7
7
9
8
7
9
思路倍增的思想：从n^2个状态里选择一些2的证书幂的位置作为代表值
状态表示：f(i,j) 表示从位置i开始的power(2,j)个数的最大值
状态转移： f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 即长度为2^
j的子区间的最大值是左右两半长度为2^j-1的长度的子区间长度的最大值中较大的一个

#include #include #include using namespace std; const int N=10010; int a[N]; int f[N][40]; int n,m; void st_prework() { for(int i=1; i<=n; i++) f[i][0]=a[i]; int t=log(n)/log(2)+1; for(int j=1; j>n>>m; for(int i=1; i<=n; i++) cin>>a[i]; st_prework(); while(m--) { int l,r; cin>>l>>r; int maxval=query(l,r); cout<

    推荐阅读


    上一篇：Kotlin 中的循环全解

    下一篇：PHP|php同比增加函数