[POJ 3250][Stack] Bad Hair Day

原題連結
無聊繼續刷水題......
總之.....一個乳牛能夠一路往右看到所有乳牛的頭頂直到某隻乳牛比他高。
我們考慮如何快速求出該乳牛的位置。
觀察到，當某隻乳牛i的高度h[i]>乳牛j的高度h[j]且i<j時，乳牛j就是頭垃圾乳牛(?
我們維護一個stack，裡面放不確定是不是垃圾乳牛的乳牛們(?，顯然高度要單調遞增。
對於乳牛i的查詢，從堆疊頂端開始把比自己矮的通通踢掉，直到一個比乳牛i高的乳牛k，那麼在i和k之間的所有乳牛i都可以看到。

每個元素最多進出堆疊1次，O(n)。

#define LL long long
#include<stack>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int maxn=80000+5;
int a[maxn];
int main()
{
    int N;
    LL ans=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++) scanf("%d",a+i);
    stack<int> S;
    for(int i=N-1;i>=0;i--)
    {
        while(!S.empty() && a[i]>a[S.top()]) S.pop();
        if(S.empty()) ans+=N-i-1; // from i+1 to N-1
        else ans+=S.top()-i-1;// from i+1 to S.top()-1
        S.push(i);
    }
    printf("%lld\n",ans);
}