题目链接： https://nanti.jisuanke.com/t/38228
题目大意：给你n个数，让你找出一个区间中f的最大值，具体的f计算方法，这段区间的和乘以这段区间的最小值。
具体思路：我们枚举每个位置，对于当前位置的数，通过二分 找出这个数作为区间最小值能够到达的最左端和最右端。如果是正数，我们直接a[i]*这段区间和就可以了，因为都是正数。
如果当前的a[i]是负数，对于这个点的右段，我们找出一个前缀和最小的点，然后对于这个点的左端，我们找出一个前缀和最大的，这样就能保证选定的区间是最小的了，负数*负数=正数。
预处理出前缀和在每段区间的最小值，最大值，以及每个区间中a[i]的最小值。
感谢qyn的讲解。
AC代码：
#include<bits/stdc++.h>
using namespace std;
# define inf 0x3f3f3f3f
# define ll long long
const int maxn = 5e5+;
ll dp1[maxn][],dp2[maxn][],dp3[maxn][];
ll a[maxn];
ll qian[maxn];
int n;
void RMQ1()
{
for(int i=; i<=; i++)
{
for(int j=; j<=n; j++)
{
if(j+(<<i)-<=n)
{
dp1[j][i]=min(dp1[j][i-],dp1[j+(<<(i-))][i-]);
}
}
}
}
void RMQ2()
{
for(int i=; i<=; i++)
{
for(int j=; j<=n; j++)
{
if(j+(<<i)-<=n)
{
dp2[j][i]=max(dp2[j][i-],dp2[j+(<<(i-))][i-]);
}
}
}
}
void RMQ3()
{
for(int i=; i<=; i++)
{
for(int j=; j<=n; j++)
{
if(j+(<<i)-<=n)
{
dp3[j][i]=min(dp3[j][i-],dp3[j+(<<(i-))][i-]);
}
}
}
}
bool judge(int l,int r,ll val)
{
int k=;
k=(int)log2((double)(r-l+));
ll tmp=min(dp1[l][k],dp1[r-(<<k)+][k]);
return tmp==val;
}
int Find_l(int pos)
{
int l=,r=pos;
int ans=pos;
while(l<=r)
{
int mid=(l+r)>>;
if(judge(mid,pos,a[pos]))
{
ans=mid;
r=mid-;
}
else
l=mid+;
}
return ans;
}
int Find_r(int pos)
{
int l=pos,r=n;
int ans=pos;
while(l<=r)
{
int mid=(l+r)>>;
if(judge(pos,mid,a[pos]))
{
ans=mid;
l=mid+;
}
else
r=mid-;
}
return ans;
}
int get_max(int l,int r)
{
int k=;
k=(int)log2((double)(r-l+));
ll tmp=max(dp2[l][k],dp2[r-(<<k)+][k]);
return tmp;
}
int get_min(int l,int r)
{
int k=;
k=(int)log2((double)(r-l+));
ll tmp=min(dp3[l][k],dp3[r-(<<k)+][k]);
return tmp;
}
int main()
{
scanf("%d",&n);
for(int i=; i<=n; i++)
{
scanf("%lld",&a[i]);
dp1[i][]=a[i];
qian[i]=qian[i-]+a[i];
dp2[i][]=dp3[i][]=qian[i];
}
RMQ1(); /// 区间最小值，在每一次询问的时候求出最左边的端点和最右边的端点
RMQ2();/// 前缀和最大值
RMQ3(); /// 前缀和最小值
ll ans=;
for(int i=; i<=n; i++)
{
int t1=Find_l(i);
int t2=Find_r(i);
if(a[i]>)
ans=max(ans,(qian[t2]-qian[t1-])*a[i]);
else
{
ans=max(ans,a[i]*(get_min(i,t2)-get_max(t1,i)));
}
}
printf("%lld\n",ans);
return ;
}