JOI 難易度11全部埋める #8 星座 3 (Constellation 3) (2020春合宿)

2次元空間上を取った風景にうつった星を条件を満たすように消すときの最小コストを求める最適化問題。

考察1

とりあえず「ビルが入らないどんな長方形領域も2つ以上の星を含まない」という条件を数式にして表す。 $x_i \le x_j$ なら、 $\min(y_i, y_j) \gt \max_{i+1 \le k \lt j} A_k$ というのが必要十分…なのだがこれはよくわからない。

「あるビルによって、そのビル以下の高さはそのビルの左右に完全に分割される」ということに思いを馳せると、高さごとにブロックたちに分け、それぞれのブロックで「そのブロックに関与する星は1個しか残っていない」という条件が満たされる必要がある。

このブロックたちはいつものようにラミナーであり、木構造として扱うことができる。ブロックの子は、その区間に包含される一段下のブロックとする。

ブロックが大量にあるじゃないか！と思うかもしれないが、ビルに邪魔されない限り複数の層間で条件が一緒になりブロックは多分 $O(N)$ 個しかないようにできる。とはいうもののイメージはつきにくいので一旦こういう層の感じで考えてみる。

ブロックがある星を関与するための必要十分条件は、ブロックがその星のx座標を含んでいて、ブロックのy座標がその星以下であるようなものである。イメージでは、星がブロックを串刺しする。

ブロックに関与する星が大量にあり、それらは1個以下しか星を残してはいけない……そんなのできるのか？？これは一般には難しい気がするが、イメージによってかなり見通しがよくなる。

ある星を残すという選択ができるときに残すとすると、その星に串刺しにされるブロックに関与する星（そして、その「関与する星」というのは上からやってくる星と、そのブロックに含まれる星の和集合である）は全部消さないといけない。ここで、その「上からやってくる星」というのは、残す星以外はもう存在しない（ある星を残すという選択ができる時点でそうなるか、すでに串刺しにされて消されたものである）ので無視してもよい。

また、串刺しにされない下層部の他のブロックは「上のブロックの星が全部消えている」という状況になる。これは良い状況で、「自分のブロックこそが夜空の天井であった」と思い込むことができて、最上位のブロック（本物の天井）と同じ状況となっている。これは再帰的な構造を示唆している。つまり、dp[ブロック]: そのブロックが天井のときの最小コストを求められれば、ブロック B について

・Bに含まれる星をすべて消すとき、dp[B] = Σ[Bの子 j] dp[j] ・Bに含まれる星 s を1つ残すとき、dp[B] = Σ[sに串刺しにされるブロック] (そのブロックが含む星のコストの合計) + Σ[s に串刺しにされるブロックたちの直接の子だが、串刺しはされていない j] dp[j]

となっている。ぬるっと考察していたがもうほぼ勝ち！

考察2

木構造でこういうことになっているので、木DPをすれば多分解ける。上の条件の後者は、串刺しの行く先の頂点が分かれば（オンライン）パスクエリとなる。特に、「Σ[s に串刺しにされるブロックたちの直接の子だが、串刺しはされていない j] dp[j]」というのは

Σ[s に串刺しにされるブロックたちの直接の子] dp[j] - Σ[s に串刺しにされるブロックたち] dp[j]

に置き換えられるので、Σ[b の直接の子] dp[j] = ep[b] とすれば、このコストは「Σ[s に串刺しにされるブロックたち (sのブロックを除く) ] (ep[j] - dp[j]) + ep[sのブロック]」となり、「Σ[sに串刺しにされるブロック] (そのブロックが含む星のコストの合計)」と合わせてパスクエリになる。

オンラインパスクエリといえばみんなだいすきHLD(+足し算の一点更新区間取得が必要なのでセグメント木 or BIT)である。ということで、木の最下層からHLDを使いながらdpを更新していける。

考察3

「ブロックが大量にあるじゃないか！と思うかもしれないが、ビルに邪魔されない限り複数の高さ間で条件が一緒になりブロックは多分 $O(N)$ 個しかないようにできる」←実装するにおいて、これも考慮する必要がある。

あるブロックが分割されるのは、ある区間の中で高さ最大のビルたちによってである。HLDにセグメント木を乗せる場合はそのまま区間maxを載せて求めることができるし、それに頼らない方法としては Cartesian Tree でも達成できると思う。時間計算量がいいのは後者。

意外に問題になるのはこの後で、ブロックの中に含まれる星を列挙する必要がある。これは木DPの遷移でそれぞれの星を見る必要があるからである。問題としては

N×N内の互いに交わらない長方形領域がたくさん与えられる。また、点がたくさん与えられる。その点はただ1つの長方形領域に含まれることが保証されている。このとき、点それぞれについて、それが含まれる長方形領域の番号を求めよ

というものである。（オフラインでもOK）

これでもJOI難易度8くらいある気がするが、平面走査で解ける。x座標の昇順に、どのy座標がどの長方形のテリトリーになっているかを管理する。一瞬遅延セグ木とかが要りそうな気がするが、std::setに (境界のy座標, 長方形のindex)を乗せればいける。ということで解けた！時間計算量は $O((N+M) \log^2 N)$ 、空間計算量は $O(N+M)$ 。