Slope Trick

[ei1333]

• [x] return min f(x)
• [x] f(x) += max(a - x, 0)
• [x] f(x) += max(x - a, 0)
• [x] f(x) += |x-a|
• [x] f(x) += a
• [x] f(x) = min f(y) (y <= x)
• [x] f(x) = min f(y) (y >= x)
• [x] f(x) = \min_{y \in [x-a,x-b]} f(y) スライド最小値
• [x] f(x) = f(x - a) 平行移動
• [x] f(x) += g(x) マージ (log1つならSplayTreeが必要）
• [ ] return f(x) (平衡二分木が必要)
• [ ] f(x) += b \times |x-a| (平衡二分木の切り張りでできそう)

他に思いつく操作　かいて

[beet-aizu]

f(x) = min_t g(t) h(x-t) convolution

[ei1333]

https://github.com/tokoharu/tokoharupage/blob/master/docs/advent2019.pdf

[ei1333]

https://twitter.com/noshi91/status/1381875703428227074