\(O(N\sqrt{N})\) 時間の別解を紹介します。

座標圧縮により \(1 \leq x_i \leq N, 1 \leq y_i \leq N\) としてよいです。

左側が \(1, \dots, N\) の \(N\) 頂点、右側が \(\overline{1}, \dots, \overline{N}\) の \(N\) 頂点からなる二部グラフを考え、座標平面上の点 \((x_i, y_i)\) を、二部グラフ上での辺 \((x_i, \overline{y_i})\) に対応させます。すると、座標平面上での辺が軸に平行な長方形は、二部グラフ上での \(C_4\)（長さ \(4\) のサイクル）に対応します。よって、グラフ上の \(C_4\) を数え上げるアルゴリズム を用いて \(O(N\sqrt{N})\) 時間で解くことができます。