POJ 3250 Bad Hair Day【単調スタック】

Bad Hair Day
Time Limit: 2000 MS
 
メモリLimit: 65536 K
Total Submissions: 24310
 
Acceepted: 8264
Description
Some of Farmer John's N cows(1≦ N ≦80,000)ar having a bad hair day!Since each cow is self-conscious about her messy hairstyle,FJ wants to count the number of other cows that can see the top of other cows'heads.
Each cow i has a specified height hi (1≦ hi ≦1,000,000)and is standing in a line of cows all facing east(to the right in our diagrams).The refore,cow ican see the tops of the heads of cows in front of her(namely cows) i＋1, i+2、and son)、for as long as these cows are stritly sharter than cow i.
Consder this example:

        =
=       =
=   -   =         Cows facing right -->
=   =   =
= - = = =
= = = = = =
1 2 3 4 5 6 

Cow(1 can see the hairstyle of cow s 2,3,4 Cow(2 can see)のcow's hairstyle Cow(3 can see the)hairstyle of cow(4 Cow)cow(4 can seeのcow)のcow's haire Cows 5
Let ci denote the number of cows hairstyle is visible from cow i;please compute the sum of c 1 through cN.For this example、the desired is answer 3+0+1+0+1+0=5.
Input
Line 1:The number of cows、 N.  Lines 2.N+1:Line i＋1 contains a single integer that is the height of cow i.
Output
Line 1:A single integer that is the sum of c 1 through cN.
Sample Input

6
10
3
7
4
12
2

Sample Output

5

ソurce
USACO 2006 November Silver
題意
一群の高さが違っている牛が左から右に並んでいます.各牛は右側のより低い牛のヘアスタイルしか見えません.もし一頭の高さがそれより大きいかそれとも同じ牛に出会ったら、この牛の後ろの他の牛を見ることができません.すべての牛がヘアスタイルの総数を見ることができることを求めます.
考え方
単調な減少スタックを維持する.現在の牛の高さがスタックの一番上の元素より小さい場合は、スタックを出します.スタックの空またはスタックの一番上の要素が現在の牛の高さより大きいまで、その結果、この時のスタック内の元素の個数を加えて、この牛のヘアスタイルが見られる牛の数量を表します.
C++コード

#include

using namespace std;

const int N=80010;
int st[N],top=0;

int main()
{
	int n,h;
	long long ans;
	while(~scanf("%d",&n))
	{
		top=0,ans=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&h);
			while(top>0&&st[top]<=h) top--;
			ans+=top;//            h      （               ） 
			st[++top]=h;
		}
		printf("%lld
",ans);
	} 
	return 0;
}