yukicoder contest 193F - ゴミ拾い Hard、Li Chao Tree 解法
問題
略解
直線（線分）の追加と最小値の計算のクエリを捌くデータ構造として紹介されがちな Li Chao Tree ですが、「任意の 2 曲線の交差が高々 1 回」という条件さえ守っていれば直線（線分）でなくても構いません。
本問では$ y = |x^3| という凸関数を平行移動したものしか考えないのでこの条件を満たします。
なお Easy の$ y = x^2 と Normal の$ y = |x| の平行移動族もこの条件を満たすので、関数を差し替えるだけで 3 問ともほぼ同じコードで AC できます。
提出
元ポスト