HDU 5443 The Water Problem RMQ

题目：http://acm.hdu.edu.cn/showproblem.php?pid=5443

题意：给定一个数组，查询区间最大值

思路：RMQ模板题

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int N = 1010;
int dp[20][N], arr[N];
void ST(int n)
{
    for(int i = 1; i <= n; i++)
        dp[0][i] = arr[i];
    for(int i = 1; (1<<i) <= n; i++)
        for(int j = 1; j <= n - (1<<i) + 1; j++)
            dp[i][j] = max(dp[i-1][j], dp[i-1][j+(1<<(i-1))]);
}
int RMQ(int l, int r)
{
    int k = log(r - l + 1) / log(2);
    return max(dp[k][l], dp[k][r-(1<<k)+1]);
}
int main()
{
    int t, n, m, a, b;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
            scanf("%d", &arr[i]);
        ST(n);
        scanf("%d", &m);
        while(m--)
        {
            scanf("%d%d", &a, &b);
            printf("%d\n", RMQ(a, b));
        }
    }
    return 0;
}