题意:
给定一个区间,每个子区间的价值为子区间的和∗ *∗子区间的最小值。求所有子区间的最大价值。区间的数都为正数。
思路:
跟上题一样,都是算贡献的题,比上题多了一个求和的操作。加一个前缀和维护就行了。
代码:
const int maxn=2e5+7; stack<PLL>stk; ll n,l[maxn],r[maxn],a[maxn],sum[maxn]; int main(){ n=read; rep(i,1,n) a[i]=read,sum[i]=sum[i-1]+a[i]; rep(i,1,n){ while(!stk.empty()&&stk.top().first>=a[i]){ stk.pop(); } if(!stk.empty()) l[i]=stk.top().second+1; else l[i]=1; stk.push({a[i],i}); } while(!stk.empty()) stk.pop(); per(i,n,1){ while(!stk.empty()&&stk.top().first>=a[i]) stk.pop(); if(!stk.empty()) r[i]=stk.top().second-1; else r[i]=n; stk.push({a[i],i}); } ll ans=0; rep(i,1,n) ans=max(ans,(sum[r[i]]-sum[l[i]-1])*a[i]); write(ans); return 0; }