POJ 2796 单调栈

题目大意：

一段区间【l,r】的价值是 (sum[r]-sum[l-1])*mini(a[i],(l<=i<=r)) 求最大代价。

单调栈。

维护一个 val,l,r代表这个以这个val为最小值，最大覆盖区间是【l,r】

维护一个单调减栈（栈顶元素到栈底元素单调递减）当新加入一个元素a[i]，如果大于栈顶的val，那么a[i]能覆盖的最左范围可以扩展到栈顶元素的最左范围。

栈顶元素出栈，新栈顶元素的最右范围可以扩展到原栈顶元素的最右范围。

 1 #include<cstdio>
 2 #include<stack>
 3 #include<iostream> 
 4 #define LL long long 
 5 #define maxn 100100
 6 using namespace std;
 7 struct Node{
 8     int val,l,r;
 9     LL s;
10 }seg[maxn];
11 LL ans=0;
12 int ansl,ansr;
13 LL sum[maxn];
14 stack<Node>a;
15 int n;
16 int main(){
17     cin>>n;
18     for(int i=1;i<=n;i++){
19         scanf("%d",&seg[i].val);
20         seg[i].l=seg[i].r=i;
21         sum[i]=sum[i-1]+seg[i].val;
22     }
23     a.push(seg[1]);
24     ans=seg[1].val,ansl=seg[1].l,ansr=seg[1].r;
25     int L,R;
26     for(int i=2;i<=n;i++){
27         while(a.size()&&a.top().val>seg[i].val){
28             L=a.top().l,R=a.top().r;
29             if(ans<(a.top().val*(sum[a.top().r]-sum[a.top().l-1]))){
30                 ans=(a.top().val*(sum[a.top().r]-sum[a.top().l-1]));
31                 ansl=a.top().l;
32                 ansr=a.top().r;
33             }
34             a.pop();
35             if(a.size())
36                 a.top().r=R;
37             seg[i].l=L;
38         }
39         a.push(seg[i]);
40     }
41     while(a.size()){
42         L=a.top().l,R=a.top().r;
43         if(ans<(a.top().val*(sum[a.top().r]-sum[a.top().l-1]))){
44                 ans=(a.top().val*(sum[a.top().r]-sum[a.top().l-1]));
45                 ansl=a.top().l;
46                 ansr=a.top().r;
47         }    
48         a.pop();
49         if(a.size())
50                 a.top().r=R;
51     }
52     cout<<ans<<endl;
53     cout<<ansl<<' '<<ansr<<endl;
54     return 0;
55 }