この解法はtesterの yuto1115 さんによるものです。

以下では、座標平面の格子点の代わりにグリッドで考えます。石が置かれている座標の最大値を \(M\) とします。

\([-1,M+1]\times[-1,M+1]\) のうち石の置かれていないマスたちを、\(1\times n\) の極大な長方形領域に分割します。

図：分割の例。黒いマスが石がある格子点を表す

これにより全体は \(O(M+N)\) 個 (または座標圧縮により \(O(N)\)個) の長方形領域に分割されます。この長方形領域同士の隣接関係に関してBFSすることで、\((-1,-1)\) から到達可能な長方形領域を列挙することを考えます。

各行ごとに長方形領域を区間 \([L,R]\) の ordered set として持つことで、上下に隣接する長方形領域を高速に求めることができるため、全体で \(\tilde{O}(N+M)\) ないし \(\tilde{O}(N)\) で答えを求めることができます。