单调栈习题

单调栈习题

I. Max answer 2019南昌邀请赛网络赛

I. Max answer 2019南昌邀请赛网络赛

链接：https://www.jisuanke.com/contest/2290/challenges 题意：给定一个长度为 n 的序列，让你选择一个区间使得区间最小值和区间和的乘积最大，问这个最大乘积是多少 思路：枚举每个点为最小值，用单调栈搜出左右两边都大于 $a[i]$ 的范围 $[l_i,r_i]$ ，然后讨论 a 的正负性。

$a_i>0$ 时，直接就是$[l_i,r_i]$这个区间的和乘上 $a_i$$a_i<0$ 时，在区间 $[l_i,r_i]$ 中找一段最小值即可 #include <bits/stdc++.h> #define ll long long using namespace std; const int maxn=5e5+10; ll n,a[maxn]; ll l[maxn],r[maxn]; ll dpmx[maxn][20],dpmn[maxn][20]; ll pref[maxn]; void rmq() { for(int i=1;i<=n;++i) dpmx[i][0]=dpmn[i][0]=pref[i]; for(int j=1;(1<<j)<=n;++j) { for(int i=0;i+(1<<j)-1<=n;++i) { dpmx[i][j]=max(dpmx[i][j-1],dpmx[i+(1<<j-1)][j-1]); dpmn[i][j]=min(dpmn[i][j-1],dpmn[i+(1<<j-1)][j-1]); } } } ll queryMax(int l,int r) { int k=log2(r-l+1); return max(dpmx[l][k],dpmx[r-(1<<k)+1][k]); } ll queryMin(int l,int r) { int k=log2(r-l+1); return min(dpmn[l][k],dpmn[r-(1<<k)+1][k]); } int main() { scanf("%lld",&n); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); int sta[maxn],top=0; for(int i=1;i<=n;++i) { while(top&&a[sta[top]]>=a[i]) top--; if(top==0) l[i]=1; else l[i]=sta[top]+1; sta[++top]=i; } top=0; for(int i=n;i>=1;--i) { while(top&&a[sta[top]]>=a[i]) top--; if(top==0) r[i]=n; else r[i]=sta[top]-1; sta[++top]=i; } for(int i=1;i<=n;++i) pref[i]=pref[i-1]+a[i]; rmq(); ll ans=-9e18; for(int i=1;i<=n;++i) { if(a[i]>0) { ll res=1ll*a[i]*(pref[r[i]]-pref[l[i]-1]); ans=max(ans,res); } else if(a[i]==0) ans=max(ans,0ll); else { ll lmin=pref[i-1]-queryMax(l[i]-1,i-1); ll rmin=queryMin(i,r[i])-pref[i]; ll res=1ll*a[i]*(rmin+a[i]+lmin); ans=max(ans,res); } } printf("%lld\n",ans); return 0; }

最后一段统计答案，也可以这样写，直接看成一个整体。$a_i<0$ 时，找左边最大和右边最小

ll ans=-9e18; for(int i=1;i<=n;++i) { ll tmp; if(a[i]>=0) { ll x=queryMin(l[i]-1,i-1); ll y=queryMax(i,r[i]); tmp=1ll*(y-x)*a[i]; } else { ll x=queryMax(l[i]-1,i-1); ll y=queryMin(i,r[i]); tmp=1ll*(y-x)*a[i]; } ans=max(ans,tmp); } cout<<ans<<"\n";