poj 2796 Feel Good (前缀和，单调栈)
题意：给出一个人n（1E5）天的情绪值（0..1E6），一段时间的value的定义是这段时间的情绪之和*这段时间情绪的最小值。
现在求value的最大值，并且输出得到这个最大值的区间。
思路：单调栈。 考虑把每一天作为最小值的时候能向左向由延伸的最远的点的下标，两个方向各做一次单调栈来预处理。和的haunted前缀和搞下。。
然后最后想着了LL,但是读入的时候前缀和的那里忘了LL wa了一发。。。2A
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月03日 星期三 19时14分42秒
4File Name :code/poj/2796.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <stack>
14#include <set>
15#include <map>
16#include <string>
17#include <cmath>
18#include <cstdlib>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34const int N=1E5+7;
35int n;
36int a[N];
37LL sum[N];
38int l[N],r[N];
39stack<int>stk;
40int main()
41{
42 #ifndef ONLINE_JUDGE
43 freopen("code/in.txt","r",stdin);
44 #endif
45
46 scanf("%d",&n);
47 sum[0] = 0 ;
48 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]),sum[i] = sum[i-1] + 1LL*a[i];
49
50 a[0]=a[n+1]=-1; //哨兵
51
52 int x;
53 stk.push(0);
54 for ( int i = 1 ; i <= n ; i++)
55 {
56 for (x=stk.top(); a[x]>=a[i] ; x=stk.top()) stk.pop();
57 l[i] = x + 1;
58 stk.push(i);
59 }
60
61 while (!stk.empty()) stk.pop();
62 stk.push(n+1);
63 for ( int i = n ; i >=1 ; i--)
64 {
65 for (x=stk.top() ; a[x]>=a[i] ; x=stk.top()) stk.pop();
66 r[i] = x-1;
67 stk.push(i);
68 }
69 LL ans = -1LL;
70 int L,R;
71 for ( int i = 1 ; i <= n ; i++)
72 {
73 LL cur = 1LL*(sum[r[i]]-sum[l[i]-1])*a[i];
74 if (cur>ans)
75 {
76 ans = cur;
77 L = l[i];
78 R = r[i];
79 }
80 }
81 printf("%lld\n%d %d\n",ans,L,R);
82
83
84 #ifndef ONLINE_JUDGE
85 fclose(stdin);
86 #endif
87 return 0;
88}