愚直解 \(O(N^2 \alpha(N))\)

街 \(a\) と街 \(b\) の間が移動可能、つまり \((x_a < x_b, y_a < y_b)\) もしくは \((x_a > x_b, y_a > y_b)\) の時に、\(a\) と \(b\) の間に無向辺を張ります。そして、各頂点ごとに自分の連結成分のサイズが答えとなります。

満点解 \(O(N \alpha(N))\)

最初に頂点を sort することで、\(x_i = i\) としてよいです。

頂点を \(x\) 座標が小さい順に見ていき、自分より \(x\), \(y\) 座標が共に小さい頂点全てと辺を張る、という操作をします。つまり、

dsu d(n);
for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++) {
        if (y[i] > y[j]) d.merge(i, j)
    }
}

という操作をします。

この操作の過程において、各連結成分のうち最も \(y\) 座標が小さいものだけ残しておけば良いことがわかります、なのでこれをsetやstackなどで管理することにより、mergeの回数をならしで \(O(N)\) 回へ減らせます。

想定解 \(O(N)\)

同様に \(x_i = i\) であるとします。

まず、連結成分の頂点のindexは\([1, 2, \dots, N]\) の連続部分列になっています。

街 \(i\) と街 \(i+1\) は、\(y_1, \dots, y_i\) が \((N, N-1, \dots, N-i + 1)\) の並び替えになっているとき、またその時のみ非連結であることが証明可能です。証明の方針としては、数学的帰納法を使い、上で説明した満点解で求めているものをより整理するとこの区切りが出てきます。

よって、\(O(N)\) でこの問題を解くことが可能です。