感觉不错
时限： 3000MS 内存限制： 65536K
案例时间限制： 1000MS
描述
比尔正在为人类的情感发展一种新的数学理论。他最近的调查致力于研究好或坏的日子如何影响人们对某个时期的记忆。
比尔最近提出了一个新想法，即为人类的每一天分配一个非负整数值。
比尔称此价值为当日的情感价值。情感价值越大，日子越好。比尔建议，生命中某个时期的价值与给定时期中某天的情感价值之和成比例，再乘以该天中某天的最小情感价值。这种模式反映出，在一个非常糟糕的日子里，平均时期的良好状况可能会大大受损。
现在，比尔正计划研究自己的生活，并找到人生中最有价值的时期。帮助他这样做。
输入项
输入的第一行包含n-他计划调查的Bill的寿命天数（1 <= n <= 100 000）。文件的其余部分包含n个整数a1，a2，…，范围从0到10 6-天的情感值。数字由空格和/或换行符分隔。
输出量
在第一行中打印比尔一生中某个时期的最大值。并且在第二行上打印两个数字l和r，以使Bill生命中第l天到第r天（含）的时间段具有最大可能的值。如果有多个具有最大可能值的期间，则打印其中任何一个。
样本输入
6
3 1 6 4 5 2
样本输出
60
3 5
分析：
先前缀和预处理……
再往左往右扩展 记录在哪个区间内为最小值
最后判断最小值 * 总和是否大于ans 更新ans
再记录当前的左右端点即为最后的区间
思路上与直方图中的最大矩形差不多……
CODE：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<stack> //栈STL函数
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
struct node{ll v,l,r; //值 左端点 右端点
}a[10000005];
stack<ll> stt; //建栈
ll n,sum[10000005],ans=0,rr=1,lll=1;
int main(){scanf("%lld",&n);for(ll i=1;i<=n;i++){scanf("%lld",&a[i].v);sum[i]=a[i].v+sum[i-1]; //预处理前缀和a[i].l=a[i].r=i; //记录坐标}for(ll i=1;i<=n;i++){while(!stt.empty()&&a[i].v<=a[stt.top()].v) //当前为最小{a[i].l=a[stt.top()].l; //记录左端点stt.pop(); //弹栈}stt.push(i); //下一个点}while(stt.empty()) stt.pop();for(ll i=n;i>0;i--){while(!stt.empty()&&a[i].v<=a[stt.top()].v){a[i].r=a[stt.top()].r; //记录右端点stt.pop(); //弹栈}stt.push(i); //下一个端点}for(ll i=1;i<=n;i++){if(a[i].v*(sum[a[i].r]-sum[a[i].l-1])>ans) //最小值*总和是否大于ans{ans=a[i].v*(sum[a[i].r]-sum[a[i].l-1]); //更新答案lll=a[i].l; rr=a[i].r; //记录当前左右端点}}printf("%lld\n%lld %lld",ans,lll,rr); //愉悦输出%%%return 0;
}