倍增、RMQ、ST算法

题目描述

给定一个长度为 NN 的数列，和 MM 次询问，求出每一次询问的区间内数字的最大值。

输入格式

第一行包含两个整数 N,M，N,M，分别表示数列的长度和询问的个数。

第二行包含 N 个整数（记为 ai​），依次表示数列的第 i项。

接下来 M 行，每行包含两个整数 li,ri​，表示查询的区间为 [li,ri]。

输出格式

输出包含 M 行，每行一个整数，依次表示每一次询问的结果。

输入输出样例

输入

8 89 3 1 7 5 6 0 81 61 52 72 61 84 83 71 8

输出

99779879

分析：

可能被查询的子区间个数：

起点有n个，对于每个起点，其后每个点都可能是终点。

共有大约n^2个子区间，但全部查找最大值不现实，利用倍增思想 起点依旧是n个，但每个区间终点只取 从起点开始的 1、2、4、8、...个数的最后一个 ，终点logn个， 实现总区间个数为n*log(n)个，预处理这些区间的最大值。   

即需要预处理的区间个数为n*log(n) （预处理时间复杂度O(n*log(n))

预处理过程用到dp。

最后 O(1)查询。              查询区间总可以用两个预处理过的区间覆盖完全（但不会多出），区间重复不影响最大值求解。

代码：

#include #include #define maxn 100009using namespace std;int dp[maxn][100]; //dp[i][j]: 从i开始的2^j次幂个数的最大值int main (){ int n,t; scanf("%d%d",&n,&t); int i,j; for(i=1; i<=n; i++) { scanf("%d",&dp[i][0]); //预处理dp数组 } for(j=1; 1<

(3条消息) 【白话系列】倍增算法_JarjingX-CSDN博客_倍增算法

//这个友链内容思想基本为本题大致思路，细品对本题理解很有帮助

//如有侵犯版权 友链作者可联系删除qaq