Bad Hair Day LeeRinji

题目链接 维护一个递减的单调栈,每次插入后当前这只牛可以被q.size()-1只左边的高于他的牛看到。

#include<cstdio>
#include<deque>
using namespace std;
const int N=8e4+9;
typedef int ll;
typedef pair<int,ll> pil;
struct MonotoneQueue:deque<pil>
{
	void push(pil p,int k)
	{
		while(!empty()&&back().second>=p.second)pop_back();
		for(push_back(p); p.first-front().first>=k;)pop_front();
	}
} q;
long long ans;
int n,h;
int main()
{
	for(scanf("%d",&n); n--;)
		scanf("%d",&h),q.push(pil(n,-h),N),ans+=q.size()-1;
	printf("%lld",ans);
}