51nod 1215 数组的宽度（单调栈）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1215

题意：

思路：

计算出以第i个数为最大值的区间范围，l_max[i]为左端点，r_max[i]为右端点，计算最小值同理可得。

计算出了区间范围，就可以计算出每个数对于答案的贡献值。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 typedef pair<int,int> pll;
14 const int INF = 0x3f3f3f3f;
15 const int maxn = 50000+5;
16 
17 int n;
18 int a[maxn];
19 
20 int sta[maxn];
21 ll l_max[maxn],r_max[maxn];
22 ll l_min[maxn],r_min[maxn];
23 
24 int main()
25 {
26     //freopen("in.txt","r",stdin);
27     while(~scanf("%d",&n))
28     {
29         for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
30 
31         int top = 0;
32         for(int i=1;i<=n;i++)
33         {
34             while(top && a[sta[top]]<=a[i])  top--;
35             if(top==0)  l_max[i]=1;
36             else l_max[i]=sta[top]+1;
37             sta[++top]=i;
38         }
39         top=0;
40         for(int i=n;i>=1;i--)
41         {
42             while(top && a[sta[top]]<a[i])  top--;  //这儿特别注意一下
43             if(top==0)  r_max[i]=n;
44             else r_max[i]=sta[top]-1;
45             sta[++top]=i;
46         }
47 
48         top = 0;
49         for(int i=1;i<=n;i++)
50         {
51             while(top && a[sta[top]]>=a[i])  top--;
52             if(top==0)  l_min[i]=1;
53             else l_min[i]=sta[top]+1;
54             sta[++top]=i;
55         }
56         top=0;
57         for(int i=n;i>=1;i--)
58         {
59             while(top && a[sta[top]]>a[i])  top--;
60             if(top==0)  r_min[i]=n;
61             else r_min[i]=sta[top]-1;
62             sta[++top]=i;
63         }
64 
65         ll ans =0;
66         for(int i=1;i<=n;i++)  ans+=a[i]*((i-l_max[i]+1)*(r_max[i]-i+1)-(i-l_min[i]+1)*(r_min[i]-i+1));
67         printf("%lld
",ans);
68 
69     }
70     return 0;
71 }