题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=0

题目描述：有一串含有N个数的数列，有M个询问，每个询问有两个数字X，Y，求出X到Y这段区间内的最大值。

输入：

第一行为一个N和M分别表示数字的个数和询问的个数，第二行为N个数。接下来M行，每行都有两个整数X，Y。

1 <= X, Y <= 1e5

输出：

输出共M行，每行输出一个数。

样例输入：

10 2

3 2 4 5 6 8 1 2 9 7

1 4

3 8

样例输出：

5

8

题目类型：RMQ

思路：

这是一道RMQ模板题，首先我们先进行RMQ预处理，即先找到每个区域内的最大值，存入dp数组中，然后根据查询直接询问dp数组

#include<bits/stdc++.h>

using namespace std;

const int N=1e6+5;

int dp[N][25];

int a[N];

int n,m,x,y;

void RMQ_build()//RMQ预处理

{

    for(int i=1;i<=n;i++)

    dp[i][0]=a[i];

    for(int j=1;(1<<j)<=n;j++)

    {

        for(int i=1;i+(1<<j)-1<=n;i++)

        dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);//找最值

    }

    return;

}

int RMQ_query(int l,int r)//查询【l,r】范围内的最大值

{

    int k=log2(r-l+1);

    return max(dp[l][k],dp[r-(1<<k)+1][k]);

}

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    RMQ_build();

    for(int i=1;i<=m;i++)

    {

        scanf("%d %d",&x,&y);

        printf("%d\n",RMQ_query(x,y));

     }

 }