玉蟾宫

wscqwq / 2023-07-25 / 原文

玉蟾宫

考虑采用悬线法,枚举矩形的下边界,然后可以预处理求得每个位置向上最多能够到达的位置。

这个问题转化为了 直方图中最大的矩形。

复杂度 \(O(nm)\)