1174 区间中最大的数

题目

解题思想

/*
rmq(动态规划思想)
*/

代码

#include<iostream>
#include<math.h>
using namespace std;
int m[10005][20];
int n;
//初始化
void work()
{
    for(int j=1; 1<<j<=n; ++j)
        for(int i=1; i+(1<<j)-1<=n; ++i)
        m[i][j] = max(m[i][j-1], m[i+(1<<(j-1))][j-1]);
}
//查询
int question(int z, int y)
{
    int x = (int)(log(y-z+1)/log(2));
    return max(m[z][x], m[y-(1<<x)+1][x]);

}
int main()
{
    cin >> n;
    int i,a,b,k;
    for(int i=1; i<=n; ++i)
        cin >> m[i][0];
    work();
    cin >> k;
    for(i=1; i<=k; ++i)
    {
       cin >> a >> b;
       cout << question(a+1,b+1) <<endl;
    }
    return 0;
}