跟大家分享最近研究 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 裡面的元素
放在資料結構內，使得解答可以快速的找出來。
此時就需要引入另外一個概念