Sanae, Cross and Color

Key observation: cuts are prefixes

The exact values of $k_1$ and $k_2$ are a red herring. Since all coordinates are integers, moving a cut inside an empty gap changes absolutely nothing. A vertical cut only determines the set

$$L=\{p_i : x_i \le k_1\},$$

and a horizontal cut only determines

$$B=\{p_i : y_i \le k_2\}.$$

The color of a point is determined by membership in $L$ and $B$. So two choices produce the same coloring iff they produce the same vertical prefix and the same horizontal prefix.

Thus, we should count pairs of distinct vertical/horizontal prefixes such that all four quadrants are nonempty.

Fix the vertical cut

Suppose the vertical cut is fixed. Let

• $L$ be points on the left,
• $R$ be points on the right.

A horizontal threshold $k$ is valid iff both $L$ and $R$ contain at least one point below/equal to $k$ and at least one point above $k$.

For a set $S$, this is equivalent to

$$\min_y(S) \le k < \max_y(S).$$

So for both sides simultaneously, $k$ must satisfy

$$\max(\min_y(L),\min_y(R)) \le k < \min(\max_y(L),\max_y(R)).$$

Define

$$lo=\max(\min_y(L),\min_y(R)),$$ $$hi=\min(\max_y(L),\max_y(R)).$$

Then valid horizontal cuts are those with

$$lo \le k < hi.$$

But we count distinct colorings, not integer values of $k$. A horizontal prefix changes only when $k$ reaches an existing $y$-coordinate. Therefore, for this fixed vertical cut, the number of distinct valid horizontal colorings is:

$$\#\{y : y \text{ appears among the points and } lo \le y < hi\}.$$

This can be answered in $O(1)$ with a prefix array over present $y$-coordinates.

Sweep vertical cuts

Coordinates satisfy $1 \le x_i,y_i \le n$, so we can bucket points by $x$ and sweep $x=1\ldots n$.

During the sweep:

• move all points with current $x$ from right to left,
• maintain $\min_y,\max_y$ for the left side,
• maintain frequencies of $y$ on the right side, plus two pointers for right-side min/max,
• after processing a nonempty $x$-bucket, we have one new distinct vertical prefix.

If the right side is still nonempty, compute

$$lo=\max(\min_L,\min_R), \qquad hi=\min(\max_L,\max_R),$$

and add

$$pref[hi-1]-pref[lo-1]$$

if $lo<hi$, where $pref[v]$ is the number of distinct present $y$-coordinates at most $v$.

No double counting happens: changing the vertical prefix changes at least one point from left-color to right-color or vice versa. Changing the horizontal prefix changes at least one point from bottom-color to top-color or vice versa. So every counted pair is a unique coloring.

Complexity

Each point is moved once, and the min/max pointers only move monotonically. Therefore the sweep is linear.

$$O(n)$$

per test case, and

$$O\left(\sum n\right)$$

over all test cases. Memory is $O(n)$. Fast, clean, no sorting tax. Nice.