あまり知られていないような気がするので書きます。欲しくなる状況自体が珍しいという話かも。
適当に調べると、傾きの単調性を使って deque で処理するやつか、先読みして Li-Chao tree で処理するやつがたくさん見つかる気がします。 先読みなし・単調性の仮定なしで、\(O(\log(n))\) time per query でやります。
メモ
ここあんまり考えてません。
よくある log 段積んで静的データ構造を動的にするテクとかでもどうにかなる？ 定数時間でクエリ処理するの自体つらそうだから log ふたつはついちゃったりしそう。
メモおわり。
定義
まず、解きたい問題を書いておきます。 以下のクエリを処理したいです。
- \(S \gets \emptyset\) で初期化。
- 与えられた \( (a, b)\) に対して \(S \gets S \cup \{(a, b)\}\) で更新。
- 与えられた \(x\) に対して \(\min_{(a, b)\in S} ax+b\) を出力。
直感的には、「xy-平面に直線を追加する」「今ある直線のうち、特定の x 座標における y 座標の最小値を答える」というものです。
この形式のクエリによって高速化できる DP があるのですが、問題例のリンクだけいくつか貼って詳細は割愛します。 AtCoder, Codeforces, AOJ
CHT というのは convex hull trick の略です。どこ発祥の呼び方なんだろう。
上記のクエリを高速に処理するデータ構造を指して CHT と言っている人や、特定の DP を上記のクエリに帰着するテクを指して CHT と言っている人がいる気がします。えびちゃん的には後者の気持ちなのですが、ここでは便宜上前者の意味で言っていそうです。
アイディア
たとえば、\(y = 2x+3\), \(y = x+1\), \(y = 3\), \(y = -x+4\), \(y = -x+5\) の直線がある状況を考えてみます。
x | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 2x+3 | -7 | -5 | -3 | -1 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | x+1 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | -x+4 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | -1 | -x+5 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
このとき、y の最小値を達成する直線がどれかを考えます。
x | -5 | -4 | -3 | -2 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 2x+3 | ** | ** | ** | ** | | | | | | | | x+1 | | | |(**)| ** | ** | ** | | | | | 3 | | | | | | | | | | | | -x+4 | | | | | | | | ** | ** | ** | ** | -x+5 | | | | | | | | | | | |
特定の直線が最小値となる x は、（高々一つの）区間になっていることがわかります。 また、傾きの降順に見ると、区間は順に並ぶことがわかります。
さらに、傾きが同じ直線が複数ある場合、y-切片が最も小さいものを採用すればよいので、傾きは distinct としてよいです。 これらをまとめて、ざっくり次のようなイメージが湧きます。
- 「この傾きに対応する最小の y-切片は？」というのを管理する
- 「この傾きの直線が最小値となる区間はあるか？ あるならどこか？」というのを管理する
- 「この区間で最小値となる直線の傾きはなにか？」というのを管理する
詳細
左側にある直線 \(y=a_lx+b_l\) と右側にある直線 \(y=a_rx+b_r\) (\(a_l \gt a_r\)) に対して、左側の方が下（同じのも含む）となるのは、 \[a_l x+b_l \le a_r x+b_r \iff x \le \frac{b_r-b_l}{a_l-a_r} \eqqcolon f(a_l, b_l, a_r, b_r)\] となります。\(x\) が整数であれば \(\lfloor\bullet\rfloor\) にしてよいです。参考袋
直線 \(y=a_mx+b_m\) も考えたとき、\(a_l \gt a_m \gt a_r\) に対して \(f(a_l, b_l, a_m, b_m) \ge f(a_m, b_m, a_r, b_r)\) となれば、\(m\) の直線（のみ）が最小となる区間はないことになります。 （雑な記法で書くとして、）\(m \lt r\) となる区間では \(m\ge l\) となっているためです。
というわけで、\( (a, b)\) の追加クエリでは次のようにします。
- 傾きを distinct にする前処理。
- \(a\) が必要か判定。
- \(a_l \gt a \gt a_r\) なる \( (a_l, b_l), (a_r, b_r) \in S\) のうち、\(a_l\), \(a_r\) が最も \(a\) に近いものを取る。
- \(a_l\) か \(a_r\) が取れない場合は \(a\) は必要なので次へ。
- \(f(a_l, b_l, a, b) \ge f(a, b, a_r, b_r)\) であれば不要なので終了。
- 上で \( (a, b')\) を消した際はここで終了しないので大丈夫。
- \(a_l \gt a \gt a_r\) なる \( (a_l, b_l), (a_r, b_r) \in S\) のうち、\(a_l\), \(a_r\) が最も \(a\) に近いものを取る。
- \(a\) によって不要になった直線の削除。
- \(a_{l'} \gt a_l \gt a\) を同様に取り、\( (a_l, b_l)\) が不要であれば取り除く。
- 不要でない \(a_l\) が見つかるまで、取り除くのを繰り返す。
- \(a \gt a_r \gt a_{r'}\) についても同様に行う。
- \(a_{l'} \gt a_l \gt a\) を同様に取り、\( (a_l, b_l)\) が不要であれば取り除く。
- \(a_l\) (if any) と \(a\) が最小となる区間の更新。
また、\(x\) の最小値クエリでは、\(x\) が含まれる区間における直線 \( (a, b)\) を探し、\(ax+b\) を返せばよいです。
各クエリは map への定数回の処理で対処できるため、\(O(\log(n))\) time です。 より詳細には、クエリ処理前時点における、必要となりうる直線の本数を \(m\) として \(O(\log(m))\) time です。
実装に関して
「傾き→切片」「傾き→区間の右端」「区間の右端→傾き」の 3 つの map を管理することになります。 このとき、「傾きを更新したが区間の右端を更新し忘れた」といったバグを防ぐため、「片方を更新したら他方も合わせて更新する」という処理をする map の wrapper を作っておくとよいかもしれません。
よしなにやって「傾き→(切片, 区間の右端)」「区間の右端→傾き」とすれば空間を若干減らせますが、実装が若干複雑になるかもしれません。
提出コード
その他
C++ での実装です。multiset を使ったり、mutable を利用していたりイテレータをがちゃがちゃやっていて少し怖いですが、実装量はとても短いです。
kactl は、KTH (Kungliga Tekniska högskolan; Royal Institute of Technology) のチームの ICPC 用ライブラリで、内容が充実しています。
感情
CHT で高速化できる DP 面白くて感動しがちだけど、数回見ると飽きがち。
CHT 初めての人は、上に貼った 3 問を考察してみてほしいです。
おわり
にゃんこ。
*1:もう少し考察して、自前の平衡二分木を実装すれば必要なくなるという説もある。
