題目鏈接：https://nanti.jisuanke.com/t/38228

題意：定義一段區間的值為該區間的和×該區間的最小值，求給定數組的最大的區間值。

思路：比賽時還不會線段樹，和隊友在這題上弄了3小時，思路大體都是對的，但就是沒法實現。這幾天惡補線段樹。

　　　首先可以利用單調棧來查找滿足a[i]為最小值的最大區間L[i]~R[i]。然后利用線段樹求一個段的和sum、最小前綴lsum和最小后綴rsum。然后遍歷a[i]:

　　　　a[i]>0:最優為sum(L[i],R[i])*a[i]

　　　　a[i]<0:最優為(sumr(L[i],i)+suml(i,R[i]-i)*a[i]

　　　這里用線段樹查詢可以用傳遞引用來求lsum和rsum，因為我們查詢一段區間是從左向右查詢的，或者可以用三個全局變量Sum、Lsum、Rsum記錄當前已找到的區間的對應屬性也行。

AC代碼：

#include<cstdio> #include<algorithm> using namespace std; const int maxn=500005; typedef long long LL;struct node{int l,r;LL sum,lsum,rsum; //sum為區間和，lsum最小前綴，rsum最小后綴 }tr[maxn<<2]; //L[i]~R[i]為滿足a[i]為最小的最大區間 int n,p,a[maxn],L[maxn],R[maxn],stk[maxn]; LL ans;node gets(node a,node b){node t;t.l=a.l,t.r=b.r;t.sum=a.sum+b.sum;t.lsum=min(a.lsum,a.sum+b.lsum);t.rsum=min(b.rsum,b.sum+a.rsum);return t; }void build(int v,int l,int r){tr[v].l=l,tr[v].r=r;if(l==r){tr[v].sum=a[r];tr[v].lsum=min(a[r]*1LL,0LL);tr[v].rsum=min(a[r]*1LL,0LL);return;}int mid=(l+r)>>1;build(v<<1,l,mid);build(v<<1|1,mid+1,r);tr[v]=gets(tr[v<<1],tr[v<<1|1]); }void query(node &x,int v,int l,int r){if(l<=tr[v].l&&r>=tr[v].r){x=gets(x,tr[v]);return;}int mid=(tr[v].l+tr[v].r)>>1;if(l<=mid) query(x,v<<1,l,r);if(r>mid) query(x,v<<1|1,l,r); }int main(){scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d",&a[i]);a[0]=a[n+1]=0xcfcfcfcf;stk[p=0]=0; //利用單調棧求L[i],R[i]for(int i=1;i<=n;++i){while(a[stk[p]]>=a[i]) --p;L[i]=stk[p]+1;stk[++p]=i;}stk[p=0]=n+1;for(int i=n;i>=1;--i){while(a[stk[p]]>=a[i]) --p;R[i]=stk[p]-1;stk[++p]=i;}build(1,1,n);for(int i=1;i<=n;++i){if(a[i]>0){node t;t.sum=t.lsum=t.rsum=0;query(t,1,L[i],R[i]);if(a[i]*t.sum>ans) ans=a[i]*t.sum;}else if(a[i]<0){LL tmp=0;node t;t.sum=t.lsum=t.rsum=0;query(t,1,L[i],i);tmp+=t.rsum;t.sum=t.lsum=t.rsum=0;query(t,1,i,R[i]);tmp+=t.lsum;tmp-=a[i];if(tmp*a[i]>ans) ans=tmp*a[i];}}printf("%lld\n",ans);return 0; }

?

轉載于:https://www.cnblogs.com/FrankChen831X/p/10784963.html

《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的2019南昌网络赛-I（单调栈+线段树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。