Bad Hair Day
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 26293 Accepted: 8997

Description

Some of Farmer John’s N cows (1 ≤ N ≤ 80,000) are having a bad hair day! Since each cow is self-conscious about her messy hairstyle, FJ wants to count the number of other cows that can see the top of other cows’ heads.

Each cow i has a specified height hi (1 ≤ hi ≤ 1,000,000,000) and is standing in a line of cows all facing east (to the right in our diagrams). Therefore, cow i can see the tops of the heads of cows in front of her (namely cows i+1, i+2, and so on), for as long as these cows are strictly shorter than cow i.

Consider this example:

    =

= =
= - = Cows facing right -->
= = =
= - = = =
= = = = = =
1 2 3 4 5 6
Cow#1 can see the hairstyle of cows #2, 3, 4
Cow#2 can see no cow’s hairstyle
Cow#3 can see the hairstyle of cow #4
Cow#4 can see no cow’s hairstyle
Cow#5 can see the hairstyle of cow 6
Cow#6 can see no cows at all!

Let ci denote the number of cows whose hairstyle is visible from cow i; plea***pute the sum of c1 through cN.For this example, the desired is answer 3 + 0 + 1 + 0 + 1 + 0 = 5.

Input

Line 1: The number of cows, N.
Lines 2…N+1: Line i+1 contains a single integer that is the height of cow i.
Output

Line 1: A single integer that is the sum of c1 through cN.
Sample Input

6
10
3
7
4
12
2
Sample Output

5

题目大意：
有n只牛，给出了n只牛的身高，每只牛往右边看，在第一只牛大于它之前它能看到几只比它矮的牛，然后对每只牛求和。
思路：
这道题很容易写出O(n^2)的朴素解法，但是会超时，那么怎么用栈将他优化到O(n)呢？
当栈为空的时候直接拆入一个元素，然后对后面的元素开始遍历
如果即将插入的元素小于栈顶元素，说明栈里面的元素全部比他高，因此栈里面的每只牛都能看见它，将答案修改为栈元素个数。
如果即将要插入的元素大于或者等于栈顶元素，退栈到栈顶元素大于它，然后此时栈里面剩下的元素全部比他高，再将答案增加栈元素个数。
那么单调栈的特点体现在哪里了呢?体现在一但栈顶元素小于即将要进栈的元素，说明栈定元素看不到后面的牛了，此时将他放在栈里面已经失去了意义，因此退栈，直到栈顶元素大于进栈元素。也就是说栈里面存的元素都是可以一个递增或者递减的序列。
代码不难，关键是要理解为什么要退栈什么时候退栈。
代码：

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn=1e5+10;
typedef long long int ll;
struct Stack{
	ll data[maxn];
	ll top;
	Stack(){
		top=-1;
	}
};
ll n,x,num;
bool isempty(Stack *&stack){
	return stack->top==-1;
}
void push(ll x,Stack *&stack){
	if(x<stack->data[stack->top]){
		stack->data[++stack->top]=x;
		num+=stack->top;
	}else{
		while(!isempty(stack)&&x>=stack->data[stack->top]){
			stack->top--;
		}
		stack->data[++stack->top]=x;
		num+=stack->top;
	}
}
int main(){
	while(scanf("%lld",&n)!=EOF){
		Stack *stack=new Stack();
		num=0;
		scanf("%lld",&x);
		stack->data[0]=x;
		stack->top++;
		n--;
		while(n--){
			scanf("%lld",&x);
			push(x,stack);
		}
		printf("%lld\n",num);
	}
}