区间的价值

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 844 Accepted Submission(s): 398

Problem Description

我们定义“区间的价值”为一段区间的最大值*最小值。

一个区间左端点在L

，右端点在R

，那么该区间的长度为(R−L+1)

。

现在聪明的杰西想要知道，对于长度为k

的区间，最大价值的区间价值是多少。

当然，由于这个问题过于简单。

我们肯定得加强一下。

我们想要知道的是，对于长度为1∼n

的区间，最大价值的区间价值分别是多少。

样例解释：

长度为1

的最优区间为2−2

答案为6∗6

长度为2

的最优区间为4−5

答案为4∗4

长度为3

的最优区间为2−4

答案为2∗6

长度为4

的最优区间为2−5

答案为2∗6

长度为5的最优区间为1−5

答案为1∗6

Input

多组测试数据

第一行一个数n(1≤n≤100000)

。

第二行n

个正整数(1≤ai≤109)

，下标从1

开始。

由于某种不可抗力，ai

的值将会是1∼109

内<b style="color:red;">随机产生</b>的一个数。（除了样例）

Output

输出共n

行，第i

行表示区间长度为i

的区间中最大的区间价值。

Sample Input

1 6 2 4 4

Sample Output

Source

2016"百度之星" - 初赛（Astar Round2B）

题意：中文题面求长度为i 的区间中最大的区间价值。区间价值=区间最小值*区间最大值

题解：1.RMQ 记录每个区间的最大值

2.滑窗处理以a[i]为最小值的左右边界

3.那么对于一个答案 a[i]*rmq(l[i],r[i]) 为此长度的答案，我们可以发现他是可以更新到小于其长度的所有长度答案的

 #include<bits/stdc++.h>

 #define ll __int64

 using namespace std;

 ll f[][];

 ll a[];

 ll l[];

 ll r[];

 ll n;

 ll ans[];

 ll aa[];

 void rmq_init()

 {

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

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

     {

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

     }

 }

 int rmq(ll aa,ll bb)

 {

     ll k=;

     ll ans1;

     while((<<(k+))<=bb-aa+)

     k++;

     ans1=max(f[aa][k],f[bb-(<<k)+][k]);

     return ans1;

 }

 int main()

 {

     while(scanf("%I64d",&n)!=EOF)

    {

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

     {

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

         f[i][]=a[i];

     }

     rmq_init();

     a[]=-;

     a[n+]=-;

     l[]=;

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

     {

         int temp=i-;

         while(a[temp]>=a[i])

             temp=l[temp]-;

         l[i]=temp+;

     }

     r[n]=n;

     for(int i=n-;i>=;i--)

     {

        int temp=i+;

        while(a[temp]>=a[i])

           temp=r[temp]+;

        r[i]=temp-;

     }

     memset(ans,,sizeof(ans));

     memset(aa,,sizeof(aa));

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

      {

         ll mm=rmq(l[i],r[i]);

         ans[r[i]-l[i]+]=max(ans[r[i]-l[i]+],mm*a[i]);

      }

      for(int i=n;i>=;i--)

         aa[i]=max(ans[i],aa[i+]);

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

        printf("%I64d\n",aa[i]);

    }

     return ;

 }

RMQ

HDU 5696 RMQ+滑窗

区间的价值