POJ 3250 Bad Hair Day（单调队列）

/*
题意：第i头牛，只能看到它右边比他矮的牛的牛头，问所有的牛能看到牛头总数

题解：从后往前搜索，队列中存储牛的最高身高，到第i头牛的时候，对队列进行一次搜索，找到比第i头牛高的牛的最小身高和所在位置j，这样j - i - 1就是第i个牛能够看到的牛头数
*/

#include <iostream>
using namespace std;
const int nMax = 80010;
const int INF = 0x7fffffff;
int h[nMax];
struct Queue
{
	int pos;
	int max;
	Queue(){}
	Queue(int pos, int max):pos(pos), max(max){}
}queue[nMax];
int front, rear;
int n;
int main()
{
	//freopen("e://data.txt", "r", stdin);
	while(scanf("%d", &n) != EOF)
	{
		for(int i = 0; i < n; ++ i)
			scanf("%d", &h[i]);
		front = rear = 0;
		queue[front ++] = Queue(n, INF);
		__int64 ans = 0;
		for(int i = n - 1; i >= 0; -- i)
		{
			int pre;
			for(int j = rear; j < front; ++ j)
			{
				if(queue[j].max < h[i])
					break;
				pre = j;
			}
			ans += queue[pre].pos - 1 - i;//②这里先记录结果再进行入队运算
			while(rear < front && queue[front - 1].max < h[i])
				front --;
			queue[front ++] = Queue(i, h[i]);
		}
		printf("%I64d\n", ans);//①原来这里出错，注意格式
	}
	return 0;
}