SlopeTrick

概要

区分線形凸関数の最小値および、最小値を与えるxの最小値と最大値を高速に求めることができるデータ構造。

区部線形凸関数の定義はmaspy氏のブログに従う。傾きが1ずつ増えていくような関数。

ここに線分を足し算したりabsを足し算したりできる（語彙力）

左、右それぞれからの累積minをとる操作もできる。

問題例

F - Absolute Minima

求められている操作が

absの加算

全体への加算

f(x)が最小値を与えるxの最小値および、そのf(x)の値

なので、まさにSlopeTrickである。

E - 花火

（編集中）