最近、凸包のトリックに関するPEG Wikiの記事を読みました。驚いたことに、この記事の最後で、行を std::set に格納すると、このトリックの完全に動的な変形(適用条件がないことを意味します) を実現できると読みました。前述のアプローチは理解できましたが、実装しようとすると必ず失敗します。
つまり、サイズ n の配列 A があり、各配列要素には 2 つの正の整数 ai と bi が含まれます。
各クエリが次の 2 つのタイプのいずれかになる Q クエリがあります。
1) 正の整数 x が与えられた場合、max (aix + bi)1 から n までのすべての i を見つける
2) いくつかの i の ai と bi の値を更新します。
更新される値は、減少しない順序になりますai1>=ai2 and bi1>=bi2 for Q >= i1 > i2 >= 1。
Update Part は、前の行を削除して新しい行を追加することで実行できます。Javaで償却された（ログn）複雑さの更新部分とクエリ部分の両方を探しています