Monge / anti-Monge な行列と CHT / Li Chao Tree の関係

導入

N \times M 行列 A が Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また、 A_{i_1, j_1} + A_{i_2, j_2} \leq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \leq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \geq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \geq A_{i_1, j_1} である。

N \times M 行列 A が anti-Monge であるとは、以下の条件が成り立つことをいう。

  • 1 \leq i_1 \lt i_2 \leq N 及び 1 \leq j_1 \lt j_2 \leq M を満たす全ての整数の組 (i_1, i_2, j_1, j_2) について、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} が成り立つ。

また同じように、 A_{i_1, j_1} + A_{i_2, j_2} \geq A_{i_1, j_2} + A_{i_2, j_1} \leftrightarrow A_{i_2, j_2} - A_{i_1, j_2} \geq A_{i_2, j_1} - A_{i_1, j_1} なので、 A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} である。

アルゴリズム

Monge でも anti-Monge でも本質的には変わらないので、なんとなく後者について説明します。

A_{i_2, j_2} \leq A_{i_1, j_2} \rightarrow A_{i_2, j_1} \leq A_{i_1, j_1} \ (i_1 \lt i_2 \land j_1 \lt j_2) より、全ての整数の組 i_1, i_2 \ (1 \leq i_1 \lt i_2 \leq N) について、 A_{i_2, k + 1} \gt A_{i_1, k + 1} かつ A_{i_2, k} \leq A_{i_1, k} を満たす k \ (1 \leq k \lt M) が高々 1 つ存在します。存在しない場合は k = M とすると、 1 \leq x \leq k について A_{i_2, x} \gt A_{i_1, x} を満たし、 k \lt x \leq M について A_{i_2, x} \leq A_{i_1, x} を満たします。

Li Chao Tree

A_{i, j} = f_i(j) とおくと、先程の式は以下のようになります。

  • 1 \leq x \leq k について f_{i_2}(k) \gt f_{i_1}(k) を満たし、 k \lt x \leq M について f_{i_2}(k) \leq f_{i_1}(k) を満たす

任意のペアについてこのような k が存在するような関数群には Li Chao Tree が使えます。証明を求められるとどう書けばいいのか困るのですが (できると思う) 、ここに書いてあるということで許してください。

codeforces.com

DAG の dp で使う場合

下三角行列なので定義域が怪しい感じになるのですが、結局 (最小値 / 最大値) クエリは定義域の中にしか飛ばさないので、適切な値で埋めれば大丈夫です。

嬉しい場合

  • オンライン dp において Monge の最大値 / anti-Monge の最小値を求めるのには LARSCH が使えなくて、その場合オンライン - オフライン変換 + SMAWK よりも定数倍が速いと思う。
  • SMAWK の書き方を忘れてしまったとき。
  • Monge な行列の列がランダムな順番で追加されるので (!?!?!?!?) min / max を求めたいとき。
  • 変なタイミングで謎の位置での最小値を求めたいとき。これは辺の重み関数が Monge かつ別のいい感じの、例えば極値が高々 1 つみたいな性質を持っている (DAG ではない) 一般の完全グラフの最短経路を求めるときに使える場合があると思っている。

Convex Hull Trick のアイデアの適用

なんだか上で満足してしまったような気分ですが、一応。

No.1867 Partitions and Inversions - yukicoder の解説はこれの特殊ケースです。

Li Chao Tree と同じく、 Monge / anti-Monge の場合ではほとんど Convex Hull Trick のロジックがそのまま使えるのですが、いくつか問題点があります。

連続する 3 つの関数のうち中央がいらない場合の判定

一次関数だとこれは定数時間でできるのですが、一般に Monge / anti-Monge となると困ります。二分探索をすればなんとかなります。なので、いわゆる「追加と質問がどちらも単調な場合」にもならし定数時間にはならない、と思っています。(特に anti-Monge でなったら LARSCH と同じ線形時間が達成できることになって、そんなことはなさそう)

追加クエリが (元の CHT でいう) 単調でない場合

こんな場合ある ??? という気持ちですが......。

CHT の場合、傾きで二分探索をして挿入するべき位置を特定していました。一般に Monge だと困ります。

N \times M 行列 A が Monge であり、その i_1, i_2 行目の任意の要素にアクセスできるので、 i_1, i_2 の大小を比較したい、という問題を考えます。これは、 i_1, i_2 行目かつ 1, M列目である A_{i_1, 1},A_{i_1, M},A_{i_2, 1},A_{i_2, M} にアクセスできればよいです。この 4 要素からなる部分行列が Monge かつ anti-Monge である場合は決定できないのですが、その場合決定しないでも問題ないです。

これで比較ができるようになったので、結局 std::map などで二分探索を用いることができます。

うれしい場合

  • 書きやすい ?
  • 条件によっては定数倍がいい気がする。