POJ2796FeelGood（单调栈模板，区间最小*区间和,皆为非负数)

传送门

题意&＃xff1a;一个序列内选一段区间&＃xff0c;该区间值&＃61;区间和*区间最小的数 &＃xff0c;使该值最大。且序列的数为非负数。
输出区间的左右端点和该区间的值&＃xff08;若有多种情况 随意输出一个&＃xff09;。

题解&＃xff1a;维护一个单调递增栈。

#include
using namespace std;
typedef long long ll;
const int N&＃61;1e5&＃43;5;
ll sum[N];int a[N],n;
int s[N];
void incr_stack(){//单调递增栈ll ans&＃61;-1;int dexl,dexr,top&＃61;0;for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i){if((!top)||a[i]>a[s[top]]) s[&＃43;&＃43;top]&＃61;i;else{while(top&&a[s[top]]>&＃61;a[i]){int dex&＃61;s[top--];ll tmp&＃61;a[dex]*(sum[i-1]-sum[s[top]]);if(ans<tmp) ans&＃61;tmp,dexl&＃61;s[top]&＃43;1,dexr&＃61;i-1;}s[&＃43;&＃43;top]&＃61;i;}}while(top){int dex&＃61;s[top--];ll tmp&＃61;a[dex]*(sum[n]-sum[s[top]]);if(ans<tmp) ans&＃61;tmp,dexl&＃61;s[top]&＃43;1,dexr&＃61;n;}printf("%lld\n%d %d\n",ans,dexl,dexr);
}
int main(){while(~scanf("%d",&n)){for(int i&＃61;1;i<&＃61;n;&＃43;&＃43;i) scanf("%d",&a[i]),sum[i]&＃61;sum[i-1]&＃43;a[i];incr_stack();}
}