单调栈&单调队列

单调栈

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

洛谷P2866 [USACO06NOV]Bad Hair Day S

题意

有$N(N\le 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$.

解析

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

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

单调队列