1541：【例 1】数列区间最大值_541:【例 1】数列区间最大值

【题目描述】
输入一串数字，给你 M 个询问，每次询问就给你两个数字 X,Y，要求你说出 X 到 Y 这段区间内的最大数。

【输入】
第一行两个整数 N,M 表示数字的个数和要询问的次数；

接下来一行为 N 个数；

接下来 M 行，每行都有两个整数 X,Y。

【输出】
输出共 M 行，每行输出一个数。

【输入样例】
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
【输出样例】
5
8
【提示】
数据范围与提示：

对于全部数据，1≤N≤105,1≤M≤106,1≤X≤Y≤N。数字不超过 C/C++ 的 int 范围。

【来源】

无

自己写的超了3个点，别人写的超了2个点，不是全过

第一次接触st表的题目，也看了一些大佬关于st表的讲解与解答，就不再自己解释和记录了（还是一条懒狗 ），不自己讲，记录又记的不清楚，算了，还是写一下吧，加深一下印象，我讲的不好，可以直接跳过我的，拉到本文最后看大佬讲的，还有，我只是了解了大概。

===================================================================
问题：给定一个长度为n的序列，有m次询问，每次给定区间[L , R]，求区间内最大值。
st表是来解决区间最值问题的，这里面涉及到倍增的思想，因为倍增可以减少搜索时间
几个关键点 ：
1.st 表，f[i][j] 是来记录从下标第i个点开始，2^j 个数之间最值，里面用到动态规划的思想
怎么记录这个表呢，加入求区间[a,b]的最值，首先要找到一个k，这里的k要取使得（不要问为什么，可能是让2个区间更可能大），这个k吧[a,b]分成2部分，即[a,a+2^k-1]和 [a+2^k,b],不难理解这部分，然后最值就是这两部分的最值。
2.查询 ，注意查询这里必须用到重叠查询，st我觉最关键的地方是重叠查询，一开始没注意，比如 max(a,b,c)可以转换成(max(a,b) max(b,c) ) 这是最重要的，接着说查询，区间[l,r] , k = log[r-l+1] 最大值 =max(f[l][k] , f[r-(1<<k)+1][k])
3.综上 初始化的时候是 f[i][j] = max(f[i][j-1] , f[ i+(1<<(j-1)) ][j-1]); 求的时候是max(f[l][k] , f[r-(1<<k)+1][k]);一加一减。

讲的也不是很清楚，做的头疼，还是菜，接下来还要学习什么线段树，树状，LCA，RMQ，感觉都是竞赛上的，但是算法课要考这些，虽然估计觉得以后用不到，但多点总没坏处，算然甲级，ccf还没怎么准备。。脑阔疼

#include<iostream>
#include<cstdio>
#include<cmath>
const int N = 1e6+5;
using namespace std;
int n,m,f[N][20],a[N],Log[N];
void init(){
	Log[1] = 0;
	for(int i=2;i<=n+1;i++) Log[i] = Log[i/2] + 1;
	for(int i=1;i<=n;i++)  f[i][0] = a[i];
	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]);
		}
	}
}
int ask(int l,int r){
	int k=Log[r-l+1];
	return max(f[l][k] , f[r-(1<<k)+1][k]) ;
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)  scanf("%d",a+i);
	init();
	int l,r;
	while(m--){
		scanf("%d %d",&l,&r);
		printf("%d\n",ask(l,r));
	}
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

参考1
参考2
参考3