問題
PDF の G です。
頂点番号が 1-indexed で振られた $N$ 頂点の木が与えられる。また、map<int, set<int>> M が空で初期化されている。以下のクエリを処理せよ;
1 X L R:M[X] = { L, L + 1, ..., R }とする。2 X:M.erase(X)とする。3 x k v_1 ... v_k: $\min \{ \mathrm{dist}(x, y) \mid \exists 1\leq i\leq k.\; \text{s.t.}\; y\in M[v_i] \}$ を出力する。そのような最小値が存在しない場合は-1を出力する。
解法
map の更新は愚直にやってよいので、問題となるのは 3 つ目のクエリです。
平方分割をします。バケットサイズを $B$ として $[1,B],[B+1,2B],\ldots,[iB+1,(i+1)B],\ldots$ というように頂点を分割します。各バケットから多始点 BFS を行うことで、すべての頂点 $u$ に対して
$$ d_u(i) = \min \{ \mathrm{dist}(u,v)\mid iB+1\leq v\leq (i+1)B \} $$
を予め計算しておきます。バケットの個数は $O(N / B)$ 個なので、計算量は $O(N ^ 2 / B)$ です。
これにより、区間 $M ( v _ i ) = [ L _ { v _ i } , R _ { v _ i } ]$ に完全に包含されるバケットについては最短距離が $O(1)$ で求まります。そして、このようなバケットの個数は $O(N/B)$ 個です。
また、$[ L _ { v _ i } , R _ { v _ i } ]$ に包含されないバケットであって、$[ L _ { v _ i } , R _ { v _ i } ]$ との共通部分が空でないものは高々 2 つであり、その区間長は $B$ 以下です。この部分に関しては LCA などを用いて一つずつ距離を求めることにすれば、$O(B \log N)$ ないし $O(B)$ で残りの部分が計算できます。
以上より、例えば $B=\sqrt N$ とすれば、タイプ 3 のクエリは $O(k\sqrt{N} \log N)$ や $O(k\sqrt{N})$ で処理することができます。
全体の計算量は $O( (N + \sum k) \sqrt{N} + Q)$ や $O( (N + \sum k \log N) \sqrt{N} +Q)$ となります。
実装
バチャ中に AC したコードそのままです。完全に包含されているブロック達の $\min$ をセグ木で計算していたり、クエリ $O(1)$ LCA を貼ったりしています。かなりごちゃごちゃしていてますが、直す気が起きず...
