跟大家分享最近研究 monotonicity、1D/1D DP、convex hull trick 的心得。
我想很多人高中的时候就搞懂了，这篇文章的主要贡献大概就是文献整理吧。
我每次看这种介绍都会被搞昏，因为有一大堆索引值。
所以我尽量的把索引值的大小关系写清楚，
一般情况下的使用会是 i < j < k < k'。
当要比较两个阵列元素的时候，我会尽量把索引值小的放左侧，
也就是我会尽量写 A[i] ?? A[j] 。
Dominatation
先从一个简单的例子开始介绍 dominate 的概念。
给定一个长度为 n 的整数阵列 A ，对所有 k 计算 A[0] ~ A[k - 1]
中的最小值，亦即计算 B[k] = min_{i < k} A[i]
首先考虑两个元素 A[i], A[j], i < j (A[i] 在 A[j] 之前)，
如果 A[i] > A[j] 的话，那对于所有 j < k, B[k] 不可能会是 A[i] 。
换句话说 A[i] 被 A[j] dominate 了，A[i] 对于 j 之后的元素是没有
影响的，因为选择 A[j] 必定是个更好的选择，所以不需要保留关于
A[i] 的资讯。
反之，如果 A[i] < A[j] ，那 A[i] 就 dominate 了 A[j] 。
因此解法很单纯，只要从 k = 0 ~ n-1 一次扫描，纪录当前的最小值即可。
再考虑一个类似的问题 (all nearest smaller values)
https://en.wikipedia.org/wiki/All_nearest_smaller_values
给定一个长度为 n 的整数阵列 A ，对于所有 k 计算出现在 A[k]
之前，最靠近 A[k] 且比 A[k] 小的数字。
亦即计算 B[k] = A[ max_{i < k : A[i] < A[k]} ]
因为必须要找到最靠近的元素，所以问题就变得比较复杂。
考虑两个元素 A[i], A[j], i < j (A[i] 在 A[j] 之前)，
A[i] > A[j] 的情况跟之前一样，但是A[i] < A[j] 的情形就不同了，
因为 A[j] 还是有可能会是 B[k], j < k 的解答。
所以可以把所有没被 dominate 的元素储存起来，计算 B[k] 的时候，
只需要从这些没被 dominate 的元素里面找解答就好。
这概念跟 Pareto frontier 的概念一样，只从比较好的候选人中挑解答。
但是 Pareto frontier 可能还是包含了许多元素，所以从 Pareto frontier
里面挑解答还是很花时间，某些时候是可以把 Pareto frontier 里面的元素
放在资料结构内，使得解答可以快速的找出来。
此时就需要引入另外一个概念