线性优化技巧学习笔记

dbxxx · 2025-08-25 02:31:23 · 算法·理论

单调栈

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

这个问题称作 NGE 问题（Next Greater Element）．用到单调栈的时候，99% 都是这个背景．应用如下：

• 若 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, 5], [2, 6]．
• 长度为 6 的线段：[1, 6]．

观察不难发现，长度为 L 的线段数，一开始为 1 且增长速度为 1，当线段触碰到 l 或 r 中的一个后增长速度变为 0，再碰到一个后变为 -1．这是两个斜线，考虑二阶差分，该操作即可变为四次单点修改．

回顾一下这个矩形问题，其实暗含的是这样一个想法：对于一个数组 a 的任意一个区间 [l, r]，考虑取 [l, r] 中的最小值 a_i 作为代表．但有一个问题是最小值有多个，所以我们考虑取 最左侧 的最小值 a_i 作为代表．

这样以来，每个区间都有唯一的代表．而上面 NLE 和 LNGE 的配合，其实就是在找对于一个 a_i，以其为代表的所有区间．它恰好是设 l_i = \operatorname{LNGE}(i) + 1，r_i = \operatorname{NLE}(i) - 1 后，[l_i, r_i] 内所有包含了 i 的子区间．由于区间代表的唯一性，这样统计出来的区间必定不重不漏．