问题 E: 天才的记忆

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

题目描述

从前有个人名叫 W and N and B,他有着天才般的记忆力,他珍藏了许多许多的宝藏。在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。题目是这样的:给你一大串数字(编号从 1 到 N ,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你M个询问,每次询问就给你两个数字A,B,要求你瞬间就说出属于A到B这段区间内的最大数。一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这位美丽的姐姐更加迷人),于是她就竭尽全力想解答这个问题。但是,她每次都以失败告终,因为这数字的个数实在是太多了!于是她请天才的你帮她解答。如果你帮她解答了这个问题,可是会得到很多甜头的哦!

输入

一个整数N表示数字的个数,接下来一行为N个数。第三行读入一个M,表示你看完那串数后需要被提问的次数,接下来M行,每行都有两个整数A,B。      

输出

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

样例输入

6

34 1 8 123 3 2

4

1 2

1 5

3 4

2 3

样例输出

34

123

123

8

提示


对于30%的数据,1<=N<=10 000,1<=M<=100。

 


对于100%的数据,1<=N<=200 000,1<=M<=10 000。

 

 

思路:建一个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;

     

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

    {

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

    }

    scanf("%d", &k);

    st_max(n);

    for(int i=1;i<=k;i++)//套板子即可

    {

        int xx,yy;

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

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

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

       }

   

}