JOI Open 2013 Synchronizationの人間的な解法を紹介します。
問題概要
略
解法
ある辺を追加すると、左右で互いに情報を交換します。この交換する個数を高速に求めたいです。
左が情報をa個、右がb個持っていて、そのうち共通のものがc個あったとします。 すると辺を追加した後、左右はつながり、合計でa+b-c個の情報を持ちます。
ところで、このcは、"その追加しようとしている辺がその前に繋がっていた時点での、左右の情報の個数"です。
以上より、辺ごとに最後につながっていた時点での左右の情報の個数を持つことにします。すると以下のようなクエリを処理できれば良くなります。
- 辺の追加
- 辺の削除
- 連結成分の頂点全体にset
- ある頂点の値を取得
これはもう今の時代どうとでもなりますが(ex euler-tour-tree)、それは今回は使いません。
まず、木の形が固定であることを利用し、最初に根付き木にすると、
- 辺の追加
- 辺の削除
- 連結成分のうち、最も根に近いものを取得
の3つができれば良くなります。連結成分のうち最も根に近い頂点の値が、その連結成分の値を表すこととします。
これはもう今の時代どうとでもなりますが、そのなかで実装の軽いeuler-tour 2Dを使用します。
これを利用すると、ノードにsetとかそこらへんを載せたsegtreeで解けることがわかります。
手元で1.9sで、まあ2xだと考えると、TLが4sぐらいならば間に合うと思うのですが、本番だとどのぐらいのTLだったのでしょうか。 まあsetをやめて、例えば先読みしてsegtreeとかにすればもっと速くなると思います。
よく考えると、RMQだけで実装できました。思考停止二分探索でlogが2個、segtree特有の二分探索高速化でlogが1個です。