线性优化技巧学习笔记

单调栈

现有一数列 $a$，请在 $\Theta(n)$ 的复杂度，对每个 $i$ 求出最小的 $j > i$ 使得 $a_j > a_i$，记为 $f_i$．若不存在这样的 $j$，记 $f_i = n + 1$．

• 若 $i$ 的 NGE 是 $j$，则 $j$ 的 LLE（Last Less） 是 $i$．在代码中的体现是，若 $j$ 将 $i$ 弹出栈，则 $i$ 的 NGE 是 $j$，$j$ 的 LLE 是 $i$．这条性质看上去很平凡，写在这里是提醒读者：单调栈中的 NGE 关系并不是单向的弹出关系，被弹的元素和弹了它的元素，是一种双向的关系．
• 若 $i$ 的 NGE 是 $j$，则 $a[i + 1 \ldots j - 1] \le a_i < a_j$．否则，$j$ 不符合 NGE 中的 N．P1823．P2866．这提示我们：考虑一个元素接下来连续的比自己小的一段 的问题，实质就是在找一个元素的 NGE，考虑单调栈．
• SP1805 HISTOGRA 条形图中的最大矩形．也是很经典的单调栈．考虑以一个矩形为顶，向左向右最多延伸多少，发现本质是 LLE 和 NLE 问题．
• P1950．考虑统计下边界在第 $i$ 行的矩形数，则问题变成 HISTOGRA 从问最大矩形变成矩形数．这个比上面的难点在于不可重复，上面的做法很明显重复了．但是思考一下上面重复的可能性：唯一一种重复的可能是存在 $a_i = a_j$，并且考虑 $a_i$ 或 $a_j$ 时，向左向右延伸会考虑到对方．
• 还是说明一下为什么这是唯一一种重复的可能．首先如果延伸的过程存在 $a_i = a_j$，那这个矩形实际上以从 $i$ 延伸和从 $j$ 延伸都会被统计到．而如果 $a_i < a_j$，则从 $a_i$ 延伸出来的矩形并不会贴到 $j$ 的顶，当然不属于从 $j$ 贴顶再延伸的矩形．
• 如何解决？考虑钦定 $a_i = a_j$ 时，如果先前会互相延伸到对方，那么现在我们只允许 $i$ 延伸到 $j$，而不允许 $j$ 延伸到 $i$．这也就意味着从 $j$ 向左延伸时，我们不再允许跨过 $a_k = a_j$，即 LLE 中 L 的严格小于应该为 LNGE，NG 代表不大于（$\le$）．这样以来，即可保证统计的不重不漏．
• ABC420F & P13647．相比于 P1950 再上难度．考虑我们每次统计的矩形，以 $(i, j)$ 为底，高度 $1 \sim u_i(j)$ 任选．现在考虑宽度为 $1$ 的矩形，宽度为 $2$ 的矩形，宽度为 $3$ 的矩形……各有多少个，这可以转化为下面这个问题：
• 线段 $[l, r]$ 上 $p \in [l, r]$，考虑 $[l, r]$ 中包含了 $p$ 的子线段，统计每种长度的数量．
• 假设 $l = 1, r = 6, p = 3$．
• 长度为 $1$ 的线段：$[3, 3]$．
• 长度为 $2$ 的线段：$[2, 3], [3, 4]$．
• 长度为 $3$ 的线段：$[1, 3], [2, 4], [3, 5]$．
• 长度为 $4$ 的线段：$[1, 4], [2, 5], [3, 6]$．
• 长度为 $5$ 的线段：$[1, 4], [2, 5]$．
• 长度为 $6$ 的线段：$[1, 6]$．