Naive solution \(O(N^2 \alpha(N))\)

Let us add an edge between vertices \(a\) and \(b\) if and only if one can move between \(a\) and \(b\), or equivalently \((x_a < x_b, y_a < y_b)\) or \((x_a > x_b, y_a > y_b)\) holds. For Vertex \(v\) the answer is the size of the connected component that contains \(v\).

Full solution \(O(N \alpha(N))\)

We can assume \(x_i = i\) by sorting the vertices first.

Let us sweep vertices in \(x\)-coordinates’ ascending order, and for a vertex \(v\) add edges between \(v\) and vertices that has less \(x\)- and \(y\)-coordinates than \(v\)’s. Specifically, do the following:

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)
    }
}

In this process, one should maintain only the vertex with the least \(y\)-coordinate for each connected component. These vertices can be maintained by e.g. set or stack, achieving \(O(N)\) merge operations in total.

The intended solution \(O(N)\)

Assume \(x_i = i\) similarly to the previous solution.

First, observe that the indices of the vertices in a connected component form a contiguous subsequence of \([1, 2, \dots, N]\).

It can be shown that City \(i\) and City \(i+1\) are not in the same connected component if and only if \(y_1, \dots, y_i\) is a rearrangement of \((N, N-1, \dots, N-i + 1)\). You can prove this by induction on \(N\) and by simplifying what Full solution above finds.

Therefore, we can solve this problem in \(O(N)\) time.