区间的价值
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
5
1 6 2 4 4
Sample Output
36
16
12
12
6
Source
题意：中文题面 求长度为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 ;
}