えびちゃんの日記

えびちゃん(競プロ)の日記です。

クエリ先読みなし任意順序 CHT

あまり知られていないような気がするので書きます。欲しくなる状況自体が珍しいという話かも。

適当に調べると、傾きの単調性を使って 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 の略です。どこ発祥の呼び方なんだろう。

アイディア

たとえば、\(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-切片は?」というのを管理する
  • 「この傾きの直線が最小値となる区間はあるか? あるならどこか?」というのを管理する
    • これは、実際には区間の右端だけ持てばよい
    • 区間が空になった傾きは捨ててよい
  • 「この区間で最小値となる直線の傾きはなにか?」というのを管理する
    • 最小値クエリに答えるのに必要になる*1
    • これは一つ上にある「傾き→区間」の逆向きの対応づけ

詳細

左側にある直線 \(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, b')\in S \wedge b' \le b\) であれば何もせず終了。
    • \( (a, b')\in S \wedge b' \gt b\) であれば \( (a, b')\) は消しておく。
  • \(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\) によって不要になった直線の削除。
    • \(a_{l'} \gt a_l \gt a\) を同様に取り、\( (a_l, b_l)\) が不要であれば取り除く。
      • 不要でない \(a_l\) が見つかるまで、取り除くのを繰り返す。
    • \(a \gt a_r \gt a_{r'}\) についても同様に行う。
  • \(a_l\) (if any) と \(a\) が最小となる区間の更新。
    • \(a_l \gt a \gt a_r\) を取り、\(f(a_l, b_l, a, b)\), \(f(a, b, a_r, b_r)\) を計算し、該当の区間を更新する。
      • \(a_l\) が取れない場合、そちらの更新は不要。
      • \(a_r\) が取れない場合、区間の右端は \(\infty\)。

また、\(x\) の最小値クエリでは、\(x\) が含まれる区間における直線 \( (a, b)\) を探し、\(ax+b\) を返せばよいです。

各クエリは map への定数回の処理で対処できるため、\(O(\log(n))\) time です。 より詳細には、クエリ処理前時点における、必要となりうる直線の本数を \(m\) として \(O(\log(m))\) time です。

実装に関して

「傾き→切片」「傾き→区間の右端」「区間の右端→傾き」の 3 つの map を管理することになります。 このとき、「傾きを更新したが区間の右端を更新し忘れた」といったバグを防ぐため、「片方を更新したら他方も合わせて更新する」という処理をする map の wrapper を作っておくとよいかもしれません。

よしなにやって「傾き→(切片, 区間の右端)」「区間の右端→傾き」とすれば空間を若干減らせますが、実装が若干複雑になるかもしれません。

提出コード

  • Library Checker :: Line Add Get Min

感情

CHT で高速化できる DP 面白くて感動しがちだけど、数回見ると飽きがち。

CHT 初めての人は、上に貼った 3 問を考察してみてほしいです。

おわり

にゃんこ。

*1:もう少し考察して、自前の平衡二分木を実装すれば必要なくなるという説もある。