Bad Hair Day【单调栈】

----------------------------From nowcoder:https://ac.nowcoder.com/acm/contest/984/A-----------------------------------

 n（1~80000），一开始写了个O(n^2)+剪的写法，果不其然地T了。折腾了一下实在想不出决定翻一下过的代码，发现是用deque做的，这才第一次接触到单调栈的题。

大致解法是：求最多看到m头牛，于是转换为求有m头牛可以被其后的牛看见。每次处理要保证栈中的牛能看见每次读入进来的牛，若新牛比原牛高则pop掉，直到遇到栈中比新牛高的牛。每次读入的牛处理后可被s.size()的牛看见。

以样例来说，一开始读一个高度为10的牛，此时栈中没有牛可以看见它，ans+=0。10入栈。

读3，可被栈中10看见，ans+=1，3入栈。

读7，可被10看见，不可被3看见，3pop掉，ans+=1，7入栈。

读4，可被10、7看见，ans+=2，4入栈。

读12，全不可见，清空栈，ans+=0，12入栈。

读2，可被12看见，ans+=1，2入栈。最后ans=5。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main()
{
    deque <int> q;
    int n;
    scanf("%d",&n);
    LL ans=0;
    for(int i=0;i<n;i++)
    {
        int x;
        scanf("%d",&x);
        while(!q.empty()&&q.back()<=x) q.pop_back();
        //printf("size:%d\n",q.size());
        ans+=q.size();
        q.push_back(x);
    }
    printf("%lld\n",ans);
}