单调结构 ​

单调栈 ​

功能 ​

维护后缀最小值序列。

支持的修改 ​

每次可以向数组末尾加一个数。

支持的查询 ​

线性复杂度查询 ​

• 每次询问的值单调不降，且始终不大于下一个要插入的数。
• 常见应用：查询某个插入数前面第一个大于当前数的位置。

对数复杂度查询 ​

对询问值没有要求，结合二分实现即可。

例题 ​

CF1988E：经典问题

• 直接二分和 st 表的做法略去，考虑怎么线性实现求 $l, r, l_2, r_2$。
• $l, r$ 分别是求前后缀第一个小于当前数的位置，经典的单调栈。
• 再考虑 $l_2$（$r_2$ 同理），即 $l$ 左边的第一个小于当前数的位置，发现查询可以满足限制（$a[l]$ 一定小于 $a[i]$）。
• 所以我们要首先让 $l$ 有单调性（便于加数），然后让查询的 $a$ 值有单调性。这需要排序。为了线性，用二维桶排即可。
• 此做法可以扩展到求 $l_k$ 和 $r_k$ 的情况。

单调队列 ​

功能 ​

维护一个线性单调变化的范围内的最值。 其实理论上，我们维护的还是后缀最小值序列，但是在很多情况下都只查询最值。