Problem Description
在缺水的地方，水是非常有限的资源，所以人们常常为争夺最大的水源而战。
给定一系列水源，用a1, a2, a3, …, an代表水源的大小。
给定一组查询，每个查询包含2 整数 L 和 R，请找出L和R之间最大的水源。
Input
输入数据首先给定一个整数T（T≤ 10 ）表示测试用例的数量。
对于每个测试用例：
首先一行是一个整数n（0 ≤ n ≤ 1000 ），代表水源数量。
然后一行是n个整数a1,a2,a3,…,an（1<=ai<=10^6）表示水源的大小。
接下来一行，有一个数字q（0 ≤ q≤ 1000 ）代表查询数量。
再之后，会有q行数据，每行两整数L和R（1 ≤ L ≤ R ≤ n ）,表示您应该在L和R之间找出最大的水源。
Output
对于每个查询，请输出代表最大水源大小的整数。
Sample input
3
1
100
1
1 1
5
1 2 3 4 5
5
1 2
1 3
2 4
3 4
3 5
3
1 999999 1
4
1 1
1 2
2 3
3 3
Sample output
100
2
3
4
4
5
1
999999
999999
1
数学-倍增（RMQ）
RMQ的板子题
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=2000;
int dp[N][10];
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
memset(dp,0,sizeof dp);
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>dp[i][0];
for(int i=1;i<=9;++i)
for(int j=1;j<=n;++j)
{
//if(j+(1<<i)-1>n) break;
if(j+(1<<(i-1))-1>n) break;
dp[j][i]=max(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
}
int q;
cin>>q;
for(int i=0;i<q;++i)
{
int l,r;
cin>>l>>r;
int t=log2(r-l+1);
//cout<<t<<'\n';
cout<<max(dp[l][t],dp[r-(1<<t)+1][t])<<'\n';
}
}
}