点$a, b$の距離を$D$とする。全体を45度回転してチェビシェフ距離の問題に読み替えると、1つの点$(x, y)$から距離$D$にある点は$x \pm D , y\pm D$で定まる正方形の辺上にある。したがって、
- $v[t] := x$座標を$t$とする点を$y$座標の昇順に並べた列
- $h[t] := y$座標を$t$とする点を$x$座標の昇順に並べた列
を持っておけば、$(x, y)$から距離$D$にある点の数は4つの列$v[x \pm D], h[y \pm D]$の二分探索で数えられる。
ただ、問題が要求しているのは、単にマンハッタン距離が$D$であるような点のペアを数えることではなく、そのような点を結ぶ無向辺があるようなグラフを考えた時、辺$\{a, b\}$を含む連結成分について同じ量を数えることである。
ただ、この設定でもBFSをしながら同じことをやればよいように見える。つまり、$a$を始点にして、上記の数え上げをしながら距離$D$にある点をキューに入れていけばよい……が、これを素朴にやると$\Omega (N^2)$になってしまう。$o(N^2)$で数えるには、一度見た頂点を再び走査しないようにするために、その都度消していく必要がある。
そこで、$h(t), v(t)$をそれぞれ昇順の配列$h_s(t), v_s(t)$と平衡二分木$h_b(t), v_b(t)$の二通りで持つことにする。キューから点$(x, y)$を初めて取り出した時、次の処理をする:
- 点$(x, y)$をすべての平衡二分木から消去する。
- $v_b[x - D], v_b[x+D], h_b[y - D], h_b[y+D]$からそれぞれ区間$[y-D, y+D], [y-D, y+D], [x-D, x+D], [x-D, x+D]$に対応する4列をsplitして取り出す。$v_b[x - D], v_b[x+D], h_b[y - D], h_b[y+D]$には残った左右の区間をmergeして入れておく。
- 4つの列上の頂点をすべてキューに入れ、$v_b, h_b$からすべて除く。
- $(x, y)$と4つの列上の点によるペアを数える。
- 配列$v_s[x-D]$の$[y-D, y+D]$に対応する区間の長さを結果に加算する。
- 配列$v_s[x+D]$の$[y-D, y+D]$に対応する区間の長さを結果に加算する。
- 配列$v_s[y-D]$の$[x-D, x+D]$に対応する区間の長さを結果に加算する。
- 配列$v_s[y+D]$の$[x-D, x+D]$に対応する区間の長さを結果に加算する。
- 正方形の4頂点$(x \pm D, y \pm D)$に穴が存在する場合は2回数えているので、重複を引く。
すべてのペアを2回ずつ数えているので、最後に2で割ることに注意。
