uva 1619 – Feel Good || poj 2796 单调栈

1619 – Feel Good

Time limit: 3.000 seconds

 Bill is developing a new mathematical theory for human emotions. His recent investigations are dedi-cated to studying how good or bad days in uent people’s memories about some period of life.A new idea Bill has recently developed assigns a non-negative integer value to each day of humanlife. Bill calls this value theemotional valueof the day. The greater the emotional value is, the betterthe day was. Bill suggests that the value of some period of human life is proportional to the sum of theemotional values of the days in the given period, multiplied by the smallest emotional value of the dayin it. This schema re ects that good on average period can be greatly spoiled by one very bad day.Now Bill is planning to investigate his own life and nd the period of his life that had the greatestvalue. Help him to do so.InputThe input will contain several test cases, each of them as described below. Consecutive test cases areseparated by a single blank line.The rst line of the input le containsn| the number of days of Bill’s life he is planning toinvestigate (1n100000). The rest of the le containsninteger numbersa1;a2;:::;anrangingfrom 0 to 106| the emotional values of the days. Numbers are separated by spaces and/or line breaks.OutputFor each test case, the output must follow the description below. The outputs of two consecutive caseswill be separated by a blank line.On the rst line of the output le print the greatest value of some period of Bill’s life.On the second line print two numberslandrsuch that the period froml-th tor-th day of Bill’slife (inclusive) has the greatest possible value. If there are multiple periods with the greatest possiblevalue, then print any one of them.SampleInput63 1 6 4 5 2SampleOutput603 5题意：得到max（一个区间的sum*min）；思路：遍历这个序列，得到以该点为最小值的区间；　　　单调栈实现；

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 100000007
#define esp 0.00000000001
const int N=1e5+,M=1e6+,inf=1e9;
ll d[N];
ll a[N];
ll l[N];
ll r[N];
ll sum[N];
void init(ll x)
{
    ll k=;
    a[]=-;
    a[x+]=-;
    for(ll i=;i<=x;i++)
    sum[i]=sum[i-]+a[i];
    k=;
    d[++k]=;
    for(ll i=;i<=x;i++)
    {
        while(a[d[k]]>=a[i])k--;
        l[i]=d[k];
        d[++k]=i;
    }
    k=;
    d[++k]=x+;
    for(ll i=x;i>=;i--)
    {
        while(a[d[k]]>=a[i])k--;
        r[i]=d[k];
        d[++k]=i;
    }
}
int main()
{
    ll x,y,z,i,t;
    int flag=;
    while(~scanf("%lld",&x))
    {
        if(flag)
        printf("\n");
        flag++;
        for(i=;i<=x;i++)
        scanf("%lld",&a[i]);
        init(x);
        ll ans=;
        ll ansl=,ansr=;
        for(i=;i<=x;i++)
        {
            ll k=(sum[r[i]-]-sum[l[i]])*a[i];
            if(k>ans)
            {
                ans=k;
                ansl=l[i]+;
                ansr=r[i]-;
            }
        }
        printf("%lld\n",ans);
        printf("%lld %lld\n",ansl,ansr);
    }
    return ;
}