hogecoder

tsutaj 競技プログラミングの記録

分割統治法メモ

はじめに

これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。

ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ)

https://hcpc-hokudai.github.io/archive/algorithm_divide_and_conquer_001.pdf

オフラインにおける分割統治

Rollback をするテク

いくつかのデータ構造では、そのデータ構造がサポートしている操作の「逆」は難しいという話があります。たとえば UnionFind では辺の追加は普通に行えますが、削除は難しいといった問題があります。では、以下のようなクエリが要求されたときはどのように解けばよいでしょうか?

$$N$$ 個の頂点があり、はじめは辺がひとつも存在しない。以下のクエリを $$Q$$ 回処理せよ。($$N, Q \leq 10^{5}$$)

  • 頂点 $$u, v$$ 間に辺が存在しないなら辺を追加する。
  • 頂点 $$u, v$$ 間に辺が存在するなら辺を削除する。
  • 頂点 $$u, v$$ が同じ連結成分に属するかどうかを判定する。

クエリがオフラインであるとき、これは普通の UnionFind と分割統治を用いて処理できます。なお、これの類題が Educational Codeforces Round #22 F: Bipartite Checking です。

クエリで与えられるそれぞれの辺 $$(u, v)$$ について、その辺がクエリ全体においていつ存在したかを区間として覚えておきます (要するに奇数回目に出てきたときに開いて、偶数回目に出てきたときに閉じるようにして区間を作る、ということです)。こうしてできた区間の数は明らかに高々 $$O(Q)$$ 個です。以降の説明ではこれを「辺区間」と呼ぶことにします。

この区間それぞれを分割統治法で処理することを考えます。クエリのインデックスの区間 $$[L, R)$$ を分割統治するとき、$$[L, R)$$ を完全に覆うような辺区間は UnionFind に反映させて、より細かい区間 $$[L, \mathrm{mid}), [\mathrm{mid}, R)$$ について再帰的に解きます。

再帰的に解くことが終わったら、$$[L, R)$$ を完全に覆っていた辺区間の情報を UnionFind から削除します。こうすることで Rollback の機能を実現できます。ここで、UnionFind から辺区間の情報を削除するときにはどうすればよいのでしょうか?これは、UnionFind における有名な計算量改善テクのひとつである、「小さい連結成分を大きい連結成分にマージ」のみをやることで実現できます (経路圧縮をやると壊れることに注意します)。実は、UnionFind ではひとつ前の状態に戻ることは簡単にできるため、これを活用すると Rollback ありの UnionFind を実現できます。

マージテクのみを用いるとき、UnionFind の中の配列であって unite の前後で値が変化しうるのは、頂点 $$u, v$$ の代表元のみです。なので、unite の前における代表元に関する値を覚えておき、削除したいときにその覚えた値に戻すことで、削除操作が実現できます。

条件の一部を強制的に満たすテク

条件を満たすペアの個数を求める問題で、満たすべき条件がひとつではなく複数存在する場合があります。この場合、分割統治法で処理できる可能性があります。

問題例はいっぱいあるので以下を解いてください (雑)

オンラインにおける分割統治

正直これは分割統治かどうか微妙なんですが・・・

区間全体に対しては簡単に解け、さらにそれぞれの要素が独立に処理できる (ある要素が他のある要素による影響を受けない) 状況で、区間の一部 $$[L, R)$$ に対して問題を解いてほしいというときに、区間をいくつかのより小さい区間に分割することで処理できる場合があります。これはオンラインでもできるため一応「オンラインにおける」分割統治と書いておきます。

以下の問題を解いてみましょう。なお、紹介している問題は Educational Codeforces Round #26 G: Functions On The Segments です。

場合分けありの一次関数 $$f_i(x)$$ が $$N$$ 個与えられ、それぞれの関数は $$1$$ から $$N$$ まで番号付けられています (詳しい一次関数の形は元の問題を読んでください)。$$l_i, r_i, x_i$$ が $$Q$$ 回与えられますので、それぞれについて $$\sum_{k=l}^{r} f_k(x)$$ の値をオンラインで求めてください。

クエリにおいて区間の範囲の制約がなく、全部に対して $$f_k(x)$$ の値を足し合わせる場合、$$x_1$$ 以下であるもの、$$x_2$$ を超えるものを求めて適当に計算すれば良いです。これと同じ発想で、与えられた区間を $$O(\log N)$$ 個の区間に分割し (そのうちのひとつを $$[L, R)$$ とします)、番号インデックスの区間 $$[L, R)$$ について、その区間に含まれる関数のみを考慮して計算する、ということをやって値を合計すれば良いです (Segment Tree と同じような発想で区間を区切ってやります)。

備忘録なので説明が雑ですみません。もし質問があれば聞いてください。