问题 A: 数列区间最大值

问题 A: 数列区间最大值

时间限制: 1 Sec  内存限制: 128 MB
提交: 39  解决: 12
[提交][状态][讨论版][命题人:add_wjl][Edit] [TestData]

题目链接：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

思路：建一个dp[i][j],i表示从i的位置开始扫描，j表示从i开始（i也包括）往后扫描（1<<j）个数

然后直接RMQ算法，输出的时候优化一下就行了。

代码：

#include<bits/stdc++.h>

using namespace std;

int n;

int dp[1000005][30];//动态规划 ，dp[i][j],j的意思是1<<j(扫描的个数)！！  j的意思是1<<j(扫描的个数)！！  j的意思是1<<j(扫描的个数)！！ 重要的事情说3遍！！！

int a[1000005];//用于存储数字

void st_max(int m)//初始化dp

{

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

    {

        dp[i][0] = a[i];//j位置为0时，相当于1<<0=1,所以在范围为1的区间里的最值就是a[i]

    }

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

    {

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

        {

            dp[i][j] = max(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);

            //这里不太好解释，就是比如i到i+(1<<j)-1个数分为2组，一组是i到 i+(1<<(j-1))-1，另一组是 i+(1<<(j-1))到i+(1<<j)-1，进行动态规划

        }

    }

}

int rmq_max(int l, int r)//取l到r区间里的最值

{

    int k = 0;

    while ((1 << (k + 1)) <= r - l + 1)k++;//找到某个k可以让2块长为（1<<k）的区间将l到r的区间完全覆盖

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

}

int main()

{

    int n;

    scanf("%d", &n);

    int k;

    scanf("%d", &k);

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

    {

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

    }

    st_max(n);

    for(int i=1;i<=k;i++)//cout卡时间，剩下就是套板子

    {

        int xx,yy;

        scanf("%d%d",&xx,&yy);

        printf("%d\n",rmq_max(xx,yy));

            //cout<<rmq_max(xx,yy)<<endl;

       }

  

}