单调栈

### 简介 单调栈比单调队列冷门很多（貌似），但思想差不多。 - [OI Wiki单调栈](https://oi-wiki.org/ds/monotonous-stack/) ### 模板：[P5788 【模板】单调栈](https://www.luogu.com.cn/problem/P5788) ### 单调栈的简单应用 - [P1901 发射站](https://www.luogu.com.cn/problem/P1901) 套模板即可 - [P2947 [USACO09MAR]Look Up S](https://www.luogu.com.cn/problem/P2947) 记得换行 - [P2866 [USACO06NOV]Bad Hair Day S](https://www.luogu.com.cn/problem/P2866) 奶牛看不到一样高的，而且记得**开long long** ### 悬线法 王知昆2003年[论文](http://www.doc88.com/p-907281104686.html)首次提出两种解决最大子矩阵问题的方法，注意两种算法的时间复杂度的区别。 - [OI Wiki悬线法](https://oi-wiki.org/misc/hoverline/) #### $\mathcal{O}(nm)$ 的算法 - [P4147 玉蟾宫](https://www.luogu.com.cn/problem/P4147) - [SP277 CTGAME - City Game](https://www.luogu.com.cn/problem/SP277) - [UVA1330 City Game](https://www.luogu.com.cn/problem/UVA1330) #### $\mathcal{O}(s^2)$ 的算法： - [P1578 奶牛浴场](https://www.luogu.com.cn/problem/P1578) ### 单调栈的思维题 - [P3467 [POI2008]PLA-Postering](https://www.luogu.com.cn/problem/P3467) - [P1823 [COI2007] Patrik 音乐会的等待](https://www.luogu.com.cn/problem/P1823) 注意这题和P2866的区别，注意处理等高的人 - [P3474 [POI2008]KUP-Plot purchase](https://www.luogu.com.cn/problem/P3474) 悬线法拓展 ### 单调栈优化 - [P5854 【模板】笛卡尔树](https://www.luogu.com.cn/problem/P5854) 单调栈优化建笛卡尔树 下面三个其实是一道题，只是输入格式和时限不同。 - [P1191 矩形](https://www.luogu.com.cn/problem/P1191) $\mathcal{O(n^4)}$ 暴力能过 - [P1950 长方形](https://www.luogu.com.cn/problem/P1950) 预处理后 $\mathcal{O(n^3)}$ 暴力能过 - [P3400 仓鼠窝](https://www.luogu.com.cn/problem/P3400) 需要 $\mathcal{O(n^2)}$ 算法 注意空间大小，卡常，开 `long long`