Max answer(The Preliminary Contest for ICPC China Nanchang National Invitational)
2024-09-08 15:12:24
Alice has a magic array. She suggests that the value of a interval is equal to the sum of the values in the interval, multiplied by the smallest value in the interval.
Now she is planning to find the max value of the intervals in her array. Can you help her?
Input
First line contains an integer n(1≤n≤5×10^5).
Second line contains nn integers represent the array a(−10^5≤ai≤10^5).
Output
One line contains an integer represent the answer of the array.
样例输入
5
1 2 3 4 5
样例输出
36
题解:
枚举每个元素作为最小值时的最优答案,然后取最大值。首先根据单调队列的思想,求出每个元素作为最小值时能够管辖的范围。
如果这个元素是正数或零,那么就是它所管辖的区间的值的和乘上该元素,因为他是正数,所以它所管辖的区间内的值均为正数。
如果这个元素是负数,那我们只需要找到
从它到它能影响到的范围的最右边前缀和的最小值-从它左边第一个元素到它能影响到的最左边的左边第一个元素这个区间前缀和的最大值,然后乘上该元素。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+;
int n,ri[maxn],le[maxn],st[maxn];
ll ans=-1e18,a[maxn],sum[maxn],mi[maxn*],ma[maxn*];
void build(int L,int R,int rt)
{
if(L==R)
{
mi[rt]=ma[rt]=sum[L];
return ;
}
int mid=(R+L)/;
build(L,mid,*rt);
build(mid+,R,*rt+);
mi[rt]=min(mi[*rt],mi[*rt+]);
ma[rt]=max(ma[*rt],ma[*rt+]);
}
ll qmi(int L,int R,int rt,int l,int r)
{
if(l<=L && R<=r) return mi[rt];
int mid=(L+R)/;
ll ret=1e18;
if(l<=mid) ret=min(ret,qmi(L,mid,*rt,l,r));
if(r>=mid+) ret=min(ret,qmi(mid+,R,*rt+,l,r));
return ret;
}
ll qma(int L,int R,int rt,int l,int r)
{
if(l<=L && R<=r) return ma[rt];
int mid=(L+R)/;
ll ret=-1e18;
if(l<=mid) ret=max(ret,qma(L,mid,*rt,l,r));
if(r>=mid+) ret=max(ret,qma(mid+,R,*rt+,l,r));
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
sum[i]=sum[i-]+a[i];
}
build(,n,);
for(int i=;i<=n;i++)
{
int cnt=i-;
while(cnt>= && a[cnt]>=a[i])
{
cnt=le[cnt];
}
le[i]=cnt;
}
for(int i=;i<=n;i++) le[i]++;
for(int i=n;i>=;i--)
{
int cnt=i+;
while(cnt<=n && a[cnt]>=a[i])
{
cnt=ri[cnt];
}
ri[i]=cnt;
}
for(int i=;i<=n;i++) ri[i]--;
/*int top=0;
for(int i=1;i<=n;i++)
{
while(top && a[st[top]]>a[i])
{
ri[st[top]]=i-1;
top--;
}
st[++top]=i;
}
while(top) ri[st[top--]]=n;
for(int i=n;i>=1;i--)
{
while(top && a[st[top]]>a[i])
{
le[st[top]]=i+1;
top--;
}
st[++top]=i;
}
while(top) le[st[top--]]=1;*/
for(int i=;i<=n;i++)
{
if(a[i]>=) ans=max(ans,a[i]*(sum[ri[i]]-sum[le[i]-]));
else
{
if(le[i]==)
{
if(i==) ans=max(ans,a[i]*a[i]);
else ans=max(ans,a[i]*(qmi(,n,,i,ri[i])-max(0ll,qma(,n,,le[i],i-))));
}
else
{
ans=max(ans,a[i]*(qmi(,n,,i,ri[i])-qma(,n,,le[i]-,i-)));
}
}
}
printf("%lld\n",ans);
return ;
}
最新文章
- Merge K Sorted Arrays
- 【教程】16岁黑客如何把Windows 95装进智能手表?【转】
- js对象、数组转换字符串
- 对Java并发编程的几点思考
- xmpp整理笔记:聊天信息的发送与显示
- org/apache/commons/discovery/tools/DiscoverSingleton
- Cocos2d-x开发实例介绍帧动画使用
- css 圆角效果
- OpenGL ES 2.0 光照
- Canvas、Paint、的简单使用及辅助类(Path、Shader、简介)
- mysql 字段注释
- 基于微博数据用 Python 打造一颗“心”
- Extjs grid 组件
- Ready!Api创建使用DataSource和DataSourceLoop的循环测试用例
- blog4go.go
- Jdk 接口类RandomAccess了解
- 用return关键字实现求和操作
- Android测试环境搭建
- java使用代理发post请求
- 【转】C# 生成二维码并且在中间加Logo(图片合并)