悬线法与单调栈

· · 个人记录

用于求解二维最大全 1 子矩形/一维最大子矩形面积

一，悬线法

分别从小到大和从大到小递推 l_i,r_i 表示 i 往左往右最远能到哪个点，由于具有传递性，可以使 l_i=l_{l_i-1}，可以证明时间复杂度 O(n)。

二，单调栈

若 a_i>a_{i+1}，则 a_i 超过的那部分完全没用，故将 i 与 i+1 合并，更新宽度计算答案。

三，笛卡尔树

以下标和权值为关键字建树，记录权值乘以子树大小的最大值。

四，说一下悬线法与单调栈。

悬线法：类似 dp，大多情况下也能用单调栈解。

单调栈：由于后面的答案一定不能恰好延伸到违反单调性的点（不在单调栈中的点），将有单调性的点（在单调栈中的点）与前面没有单调性的点的贡献合并（在本题中是宽度）。