https://www.51nod.com/Challenge/Problem.html#!#problemId=1174
给出一个有N个数的序列，编号0 - N - 1。进行Q次查询，查询编号i至j的所有数中，最大的数是多少。
例如: 1 7 6 3 1。i = 1, j = 3，对应的数为7 6 3，最大的数为7。（该问题也被称为RMQ问题）
输入
第1行：1个数N，表示序列的长度。(2 <= N <= 10000)
第2 - N + 1行：每行1个数，对应序列中的元素。(0 <= S[i] <= 10^9)
第N + 2行：1个数Q，表示查询的数量。(2 <= Q <= 10000)
第N + 3 - N + Q + 2行：每行2个数，对应查询的起始编号i和结束编号j。(0 <= i <= j <= N - 1)
输出
共Q行，对应每一个查询区间的最大值。
输入样例
5
1
7
6
3
1
3
0 1
1 3
3 4
输出样例
7
7
3

线段树

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
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;
#define M 10000+5
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int MAX[M<<2];
inline void PushPlus(int rt){
	MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
} 
void Build(int l,int r,int rt){
	if(l==r){
		scanf("%d",&MAX[rt]);
		return ;
	}
	int m=(l+r)>>1;
	Build(lson);
	Build(rson);
	PushPlus(rt);
}
int Query(int L,int R,int l,int r,int rt){
	if(L<=l&&r<=R){
		return MAX[rt];
	}
	int m=(l+r)>>1;
	int ans=0;
	if(L<=m)
		ans=max(ans,Query(L,R,lson));
	if(R>m) 
		ans=max(ans,Query(L,R,rson));
	return ans;
}
int n,m,i,j;
int main(){
	freopen("in","r",stdin);
	scanf("%d",&n);
	Build(1,n,1);
	scanf("%d",&m);
	while(m--){
		scanf("%d%d",&i,&j);
		printf("%d\n",Query(i+1,j+1,1,n,1));
	} 
	return 0;
}