问题 E: 天才的记忆

问题 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;

       }

   

}