AtCoder Grand Contest 002: D - Stamp Rally

http://agc002.contest.atcoder.jp/tasks/agc002_d

解法

二分探索をすることを考えてみよう。すると i 番目までの辺を使った UnionFind が欲しくなる。でもあらかじめ全部作るのは難しい。 そこで Parallel Binary Search という手法を使う（Parallel Binary Search という名前が正しいかはよく分からない）。

動作の雰囲気をシミュレーションしたものを以下のページに置いといた。javascript の canvas で作っているので、IE のバージョン次第では見れないかも。

https://pekempey.github.io/parallel_binary_search/simulate.html

---

i 番目までの辺を使った UnionFind を全部作るのは難しいと言ったが、これを可能にするのが永続 Union Find。

半永続（最新版しか更新できない）であれば更新時間の配列を使って簡単に実装できる。

本番中自分が投げたのは完全 16 分木の永続配列を用いた全永続（最新版以外の更新も可能）の Union-Find。計算量とメモリの効率が良くないのだが、直感的なのでこっちを使ってる。

コード中で i 番目までの UnionFind を ufs[i] に入れるというコードを書いている。

vector<UnionFind> ufs(m + 1);
UnionFind uf(n);
 
for (int i = 0; i < m; i++) {
    int a, b;
    scanf("%d %d", &a, &b);
    a--;
    b--;
    uf.merge(a, b);
    ufs[i + 1] = uf;
}

コードを見れば分かるように、見た目上はコピーが高速な UnionFind である。

8 分木に変えた実装が以下のコード。大体 1583 ms (111,872 KB)。2 分木でも高速な実装をすれば早くなるかな。

割と応用が効きそうなテクニックだ。