讓你計算所有連續(xù)子序列的最大值-最小值的和。

?(單調(diào)棧)

對于一個數(shù)Ai來講，如果其有貢獻(xiàn)的價值，要么是-Ai作為最小值，要么是Ai作為最大值。 那么Ans=ΣAi*maxn-Ai*minn. void work() {top=1,S[1]=P(N,0);F(i,1,n){while(S[top].first<=a[i])top--;l[i]=S[top].second+1;S[++top]=P(a[i],i);}top=1,S[1]=P(N,n+1);for(int i=n;i;i--){while(S[top].first<a[i])top--;r[i]=S[top].second-1;S[++top]=P(a[i],i);}F(i,1,n)ans+=1ll*a[i]*(i-l[i]+1)*(r[i]-i+1); }int main(){scanf("%d",&n);F(i,1,n)scanf("%d",a+i);work();F(i,1,n)a[i]*=-1;work();printf("%lld\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/planche/p/9428182.html

總結(jié)

以上是生活随笔為你收集整理的D. Imbalanced Array的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。