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
因為資料是随機的,是以可以水過去。
用單調隊列的n*n的方法。
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 2e5 + 10;
int n, a[maxn];
int p1[maxn],p2[maxn];
int l,r,mx,my;
int q,h,qq,hh;
LL ans;
int main()
{
while (~scanf("%d",&n))
{
l=r=1;
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if (a[i]>a[l])
{
l=r=i;
mx=my=a[i];
}
}
printf("%I64d\n",ans=(LL)a[l]*a[r]);
for (int i=2;i<=n;i++)
{
if (l>1&&a[l-1]<=my&&a[l-1]>=mx)
{
--l; printf("%I64d\n",ans); continue;
}
if (r<n&&a[r+1]<=my&&a[r+1]>=mx)
{
++r; printf("%I64d\n",ans); continue;
}
q=qq=0; h=hh=-1; ans=0;
for (int j=1;j<=n;j++)
{
while (q<=h&&a[p1[h]]<a[j]) --h;
p1[++h]=j;
while (qq<=hh&&a[p2[hh]]>a[j]) --hh;
p2[++hh]=j;
while (p1[q]+i<=j) ++q;
while (p2[qq]+i<=j) ++qq;
if (j<i) continue;
if ((LL)a[p1[q]]*a[p2[qq]]>ans)
{
ans=(LL)a[p1[q]]*a[p2[qq]];
l=j-i+1; r=j;
my=a[p1[q]]; mx=a[p2[qq]];
}
}
printf("%I64d\n",ans);
}
}
return 0;
}
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef __int64 LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, n, a[maxn], L[maxn], R[maxn], dp[maxn][20], lg[maxn];
LL ans[maxn];
int get(int l, int r)
{
int k = lg[r - l + 1];
return max(dp[l][k], dp[r - (1 << k) + 1][k]);
}
int main()
{
lg[1] = 0;
for (int i = 2; i < maxn; i++) lg[i] = lg[i >> 1] + 1;
while (scanf("%d", &n) != EOF)
{
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), dp[i][0] = a[i], ans[i] = 0;
for (int i = 1; (1 << i) <= n; i++)
{
for (int j = 1; j + (1 << i) - 1 <= n; j++)
{
dp[j][i] = max(dp[j][i - 1], dp[j + (1 << i - 1)][i - 1]);
}
}
stack<int> p;
for (int i = 1; i <= n; i++)
{
while (!p.empty() && a[p.top()] > a[i])
{
R[p.top()] = i - 1; p.pop();
}
p.push(i);
}
while (!p.empty()) R[p.top()] = n, p.pop();
for (int i = n; i; i--)
{
while (!p.empty() && a[p.top()] > a[i])
{
L[p.top()] = i + 1; p.pop();
}
p.push(i);
}
while (!p.empty()) L[p.top()] = 1, p.pop();
for (int i = 1; i <= n; i++)
{
int len = R[i] - L[i] + 1;
ans[len] = max(ans[len], 1LL * a[i] * get(L[i], R[i]));
}
for (int i = n - 1; i; i--) ans[i] = max(ans[i], ans[i + 1]);
for (int i = 1; i <= n; i++) printf("%I64d\n", ans[i]);
}
return 0;
}