note

Convex Layers

はじめに

この記事は https://codeforces.com/blog/entry/75929 の雑な意訳です
詳細な証明が欲しい方はそちらを見ることをお勧めします

Convex Layers とは

相異なる点の集合が与えられ、「凸包を取っては含まれる集合を削除すること」を繰り返すとき、各点が何回目の操作で削除されるかを求める問題
(参考:https://en.wikipedia.org/wiki/Convex_layers )

f:id:tk0_math:20210120202916p:plain

機能

一点削除: $O( \log ^2 N)$
左側凸包: $O(k \log ^2 N) (k : 凸包に用いられる点の個数)$

このデータ構造を左側と右側で2つ持って、各階層で管理すれば計算量 $O(N \log ^2 N)$ でConvex Layersが解けます

左側凸包

次の分割統治を考えることで高速に構築することができます

y座標でソートして、集合を半分に分割する
2つの集合に対して再帰的に凸包を作る
凸包同士をつなげる「橋」を見つける (これは二分探索で $O( \log N)$ で可能)
橋に被覆された凸包を無視する

凸包を動的に管理するために、分割統治をSegment Treeの形に置き換えます
各ノードには点集合の範囲と、子同士の凸包をつなぐ橋の端点のみを保持することにします

橋の見つけ方

始めに、 $p$ を集合の下半分、 $q$ を上半分を表すノードに初期化します
$p,q$ どちらもセグ木の「葉」に到達するまで下の探索を繰り返します

$p$ の橋を $\{ a,b \}$ 、 $q$ の橋を $\{ c,d \}$ として、以下の6通りに場合分けします
(i) $a \neq b$ かつ $a,b,c$ が反時計回りに位置する
$p$ を、 $p$ の上半分の子に更新する

(ii) $c \neq d$ かつ $b,c,d$ が反時計回りに位置する
$q$ を、 $q$ の下半分の子に更新する

(iii) $a = b$
$q$ を、 $q$ の上半分の子に更新する

(iv) $c = d$
$p$ を、 $p$ の下半分の子に更新する

(v) $ab$ と $cd$ の交点が上半分に属する
$q$ を、 $q$ の下半分の子に更新する

(vi) $ab$ と $cd$ の交点が下半分に属する
$p$ を、 $p$ の上半分の子に更新する

f:id:tk0_math:20210120212848p:plain

それぞれのケースについて、使わない集合が橋に用いられないことは容易に確認できます
1回の更新で $p,q$ のいずれかが葉に近づくので、橋の探索は $O(\log N)$ で終わります

各ノードについて橋の端点が分かれば、凸包は先ほどの分割統治と同様の再帰を行うことで、 $O(k \log ^2 N)$ が達成できます

一点削除

実はそこまで難しくなく、対応するノードを存在しなかったことにして、根まで遡りながらノードを更新していけばよいです

実装例

https://judge.yosupo.jp/submission/36284