【CodeVS3098】badhair

Description

有 N(1 ≤n ≤ 80,000) 头很关注自己发型的牛 站在一排 ，望着同一个方向。 每头牛都 有一个高度 hi (1 ≤ hi ≤ 1,000,000,000) 。每头牛只能看见自己前方比自己矮的的发型。请计算出所有牛能看到的发型总数

Input

第一行个整数： N
接下来 N行：每一个整数，表示第 i头牛的高度 hi

Output

一个整数，表示所有的牛能看到发型总。

Sample Input

6
10
3
7
4
12
2

Sample Output

5

HINT

1 ≤ N  ≤ 80,000

题解

维护一个单调递减的栈，栈的大小就是每个奶牛最多被看到多少次。

#include<iostream>
#include<cstdio>
#define N 80010
using namespace std;
long long s[N];
long long n,x,top,ans;
int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        while (top && x>=s[top])
            top--;
        ans += top;
        s[++top] = x;
    }
    cout<<ans;
}