问题2030--区间最大值

2030: 区间最大值

时间限制: 3 Sec  内存限制: 512 MB
提交: 55  解决: 9
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一个长度为N的数组a[]，数组元素分别为a1、a2、···，an。现有Q个询问，每个询问包含一个区间，请回答该区间的最大值为多少。

输入

第1行包含两个正整数N、Q，分别表示数组a的长度和询问的个数。
第2行包含Ｎ个非负整数a1、a2、···，aN，表示数组a中元素的值。
第3~第Q+2行每行表示一个询问，每个询问包含两个整数L、R，表示区间的左右端点。
1≤N，Q≤5×105,1≤L≤R≤N，-109≤ai≤109。

输出

共Q行，每行包含一个整数，表示相应询问的答案。

样例输入 Copy 

5 5
1 2 3 4 5
1 1 
1 2 
1 3
3 4
2 5

样例输出 Copy 

1
2
3
4
5

来源/分类

基础算法 ST算法 
[提交] [状态]