1 /*
2 * DA-term-Bad Hair Day.cpp
3 *
4 * 这是一种解法，还可以用 “单调队列” 来做(见后。。)
5 *
6 * Created on: 2011-12-2
7 */
8
9 #include <iostream>
10 using namespace std;
11
12 const int maxn = 80000 + 5;
13
14 int h[maxn], n;
15 int num[maxn], cow[maxn]; //num[i]:第i头牛能看到的牛数
16 //cow[i]:在第i头牛东边第一个比i高的牛
17
18 int main(){
19 cin >> n;
20
21 for(int i=0; i<n; i++)
22 cin >> h[i];
23
24 unsigned long long ans = 0; //用long long
25 int i, k;
26 num[n-1] = 0; cow[n-1] = -1;
27
28 for(i=n-2; i>=0; i--){
29 if(h[i] < h[i+1]){
30 num[i] = 0; cow[i] = i+1;
31 }
32 else{
33 k = i + 1;
34 while(k != -1 && h[k] < h[i]){
35 num[i] += (num[k] + 1);
36 k = cow[k];
37 }
38 cow[i] = k; //注意更新cow
39 ans += num[i];
40
41 }
42 }
43
44 //printf("%ld\n", ans); //printf(“%u”, ans);
45 cout << ans << endl;
46
47 return 0;
48 }
//单调队列法：
1 #include <iostream>
2 //#include <cstdio>
3 using namespace std;
4
5 const int maxn = 80 + 5;
6 const int inf = 1000000000 + 2;
7
8 unsigned long long ans = 0;
9 int h[maxn], monoq[maxn], n;
10
11 int main(){
12 //scanf("%d", &n);
13 cin >> n;
14
15 int tail = -1;
16 h[n] = inf;
17 for(int i=0; i<n; i++){
18 //scanf("%d", &h[i]);
19 cin >> h[i];
20 }
21
22 for(int i=0; i<=n; i++){
23 while(tail >= 0 && h[monoq[tail]] <= h[i]){ //用 <=
24 ans += (i - monoq[tail] - 1);
25 tail--;
26 }
27 monoq[++tail] = i;
28 }
29
30 //printf("%u\n", ans);
31 cout << ans << endl;
32
33
34
35 return 0;
36 }