POJ 3250 Bad Hair Day

题目链接： http://poj.org/problem?id=3250

分析：单调栈入门。

依次向前模拟，直到找到比自己高的。

因为维护的是单调栈，那么就会保证之前的都能看到自己，统计答案，把该数放进栈中即可。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <stack>
typedef long long ll;
static const int MAXN=100050;
using namespace std;
ll n,x,num,ans,s[MAXN];
inline void solve(ll x)
{
    while(s[num]<=x&&num) num--;
    ans+=num;
    s[++num]=x;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        solve(x);
    }
    printf("%lld\n",ans);
    return 0;
}