読者です 読者をやめる 読者になる 読者になる

AOJ 2667 Tree (クエリ平方分割解法)

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2667

解法

クエリをB個ごとのブロックに分割する。ブロックのはじめにやる処理をSetUp,ブロックのおわりにやる処理をTearDownと呼ぶことにする。

SetUp

ブロック内のクエリで関係する頂点だけを使って,縮約されたO(B)頂点の森を作る。ブロック内のクエリで関係する頂点とは,具体的には以下のとおり。

  • addクエリで指定された頂点v
  • distanceクエリで指定された2つの頂点u, vLCA(u,v)

この処理はO(N)でできる。

クエリ処理

addクエリ

addLazyという配列を作っておき,addLazy[v] += xとする。

distanceクエリ

根からu, v, LCA(u,v)までの距離が分かればよい(「その他の解法」のリンク参照)ので,根から頂点xまでの距離を計算する方法を考える。これは縮約された森でxから根まで辿ることで,以下のような方法で計算できる。

ans = 0
y = x
while y has parent:
  y = parent(y)
  ans += addLazy[y] * (depth(x) - depth(y))

return ans + addCurrent[x]

addCurrentの意味はTearDownで説明する。parentは縮約された森での親,depthはもともとの木での頂点の深さである。

縮約された森では頂点数はO(B)個なので,この処理はO(B)でできる。

TearDown

もともとの木の根から葉の方向にaddLazyの値を伝搬させて,addCurrentという配列に「もともとの木での根から頂点xまでの距離」が格納された状態にする。

その後でaddLazyを0で埋める。

この処理はO(N)でできる。

計算量

  • SetUpはO(N)の計算量で,O(Q/B)回呼び出される
  • addクエリはO(1)の計算量で,O(Q)回呼び出される
  • distanceクエリはO(B)の計算量で,O(Q)回呼び出される
  • TearDownはO(N)の計算量で,O(Q/B)回呼び出される

B=O(\sqrt{Q})程度に設定すると,全体としてO((Q+N)\sqrt{Q})

コード

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1571415

定数倍高速化をして,B=3\sqrt{Q}程度にすると2.93secで通った。(何も工夫しないと8secくらいかかって通らなかった)

参考

プログラミングコンテストでのデータ構造 2 ~動的木編~

クエリ平方分割について載っています

その他の解法