单调栈

一种内部元素具有单调性的栈

洛谷P2866 [USACO06NOV]Bad Hair Day S

题意

有\(N (N \leq 80000)\)头奶牛，每一头牛都站在一排，身高为\(h_i\)。
对于第\(i\)头牛前面的第\(j\)头牛，如果\(h_i>h_{i+1}\)并且\(h_i>h_{i+2}\) \(\cdots\) \(h_i>h_j\)，那么认为第\(i\)头牛可以看到第\(i+1\)到第\(j\)头牛。

定义\(C_i\)为第\(i\)头牛所能看到的别的牛的数量。请帮助农夫约翰求出\(\sum_{i=1}^n C_i\).

解析

考虑一头牛能被几头牛看到。

形象地来说，就是如果一个人比你小，还比你强，那你就可以退役了

单调队列