区间的价值
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
一个区间左端点在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>的一个数。（除了样例）
第一行一个数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]) 为此长度的答案，我们可以发现他是可以更新到小于其长度的所有长度答案的
1 #include<bits/stdc++.h> 2 #define ll __int64 3 using namespace std; 4 ll f[100005][50]; 5 ll a[100005]; 6 ll l[100005]; 7 ll r[100005]; 8 ll n; 9 ll ans[100005]; 10 ll aa[100005]; 11 void rmq_init() 12 { 13 for(int j=1;(1<<j)<=n;j++) 14 for(int i=1;i+(1<<(j))-1<=n;i++) 15 { 16 f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]); 17 } 18 } 19 int rmq(ll aa,ll bb) 20 { 21 ll k=0; 22 ll ans1; 23 while((1<<(k+1))<=bb-aa+1) 24 k++; 25 ans1=max(f[aa][k],f[bb-(1<<k)+1][k]); 26 return ans1; 27 } 28 29 int main() 30 { 31 while(scanf("%I64d",&n)!=EOF) 32 { 33 for(int i=1;i<=n;i++) 34 { 35 scanf("%I64d",&a[i]); 36 f[i][0]=a[i]; 37 } 38 rmq_init(); 39 a[0]=-1; 40 a[n+1]=-1; 41 l[1]=1; 42 for(int i=2;i<=n;i++) 43 { 44 int temp=i-1; 45 while(a[temp]>=a[i]) 46 temp=l[temp]-1; 47 l[i]=temp+1; 48 } 49 r[n]=n; 50 for(int i=n-1;i>=1;i--) 51 { 52 int temp=i+1; 53 while(a[temp]>=a[i]) 54 temp=r[temp]+1; 55 r[i]=temp-1; 56 } 57 memset(ans,0,sizeof(ans)); 58 memset(aa,0,sizeof(aa)); 59 for(int i=1;i<=n;i++) 60 { 61 ll mm=rmq(l[i],r[i]); 62 ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],mm*a[i]); 63 } 64 for(int i=n;i>=1;i--) 65 aa[i]=max(ans[i],aa[i+1]); 66 for(int i=1;i<=n;i++) 67 printf("%I64d ",aa[i]); 68 } 69 return 0; 70 }