座標を \(45\) 度回転させ、マンハッタン距離ではなくチェビシェフ距離で考えます。こうしても答えは変わりません。

以下の問題が解ければ、二分探索で元の問題の答えも求められます。

\((a_i,b_i)\) から距離 \(\text{mid}\) 以内にあるクリスマスツリーの個数は？

公式解説では並列二分探索というテクニックを使っていますが、ここでは直接この問題を解くことを考えます。

クリスマスツリーを \(x\) 座標の昇順にソートしたものを考えると、\(x\) 座標に注目した時に答えになりうる区間は \(2\) 回の二分探索により求められます。その中で、\(y\) 座標が所定の区間に入っているものの個数を求められればよいです。

これはWavelet Matrixというデータ構造を用いて高速に実現できます。