ABC196 E Filters
ABC189 E Rotate and Flipのように考える. 一旦多項式の形にして考察すると, $ xの値によって$ N個以下に場合分けでき, $ xが含まれるのはそのうちの一つであるということがわかる. このままでも二分探索を用いることで解ける. またさらに考察すると, 求める関数は折れ線構造をしており, 高々3個の場合分けで良いことがわかる. よってこれをそのまま実装すればよい. また, SegmentTree Beatsというデータ構造を用いて殴ることもできる.