2285. Where Horizontal Meets Vertical

n segments are given. Every one is axis-aligned and has positive length, so each is either horizontal or vertical and never both. Count the pairs made of one horizontal and one vertical segment that share at least one point.

Pairs of parallel segments are NOT counted, even when they overlap. That is the whole rule, and it is what makes the problem have a sweep solution: two perpendicular axis-aligned segments meet exactly when

h.xlo <= v.x <= h.xhi and v.ylo <= h.y <= v.yhi

both of which are interval containments and neither of which needs a cross product at all.

(0,0)-(4,0) horizontal, (2,-2)-(2,2) vertical, (6,-2)-(6,2) vertical -> 1

## What most people try first

The double loop: every horizontal against every vertical, two interval tests each. It is correct and it is O(n^2). At n = 200000 split evenly that is 10^10 pair tests, which no judge will wait for. The point of this problem is that the pair COUNT can be found without looking at the pairs.

The second attempt is an x-sorted scan that keeps a running count of open horizontal segments and multiplies. That gets the x condition right and ignores y entirely, so it counts every open horizontal rather than those whose height lies inside the vertical segment's span.

## Sweep along x, and ask about y

Walk a vertical sweep line from left to right. A horizontal segment is ACTIVE while the sweep is between its two x values, and the question at a vertical segment sitting at x = v.x is: how many active horizontal segments have their y inside [v.ylo, v.yhi].

That is a count of values in a range, over a set that gains and loses members. A Fenwick tree answers it in O(log n) per operation, indexed by y. The y values are as large as 10^6 and may be negative, so index by RANK rather than by value: collect the heights of the horizontal segments, sort them, remove duplicates, and let position k + 1 of the tree stand for the k-th distinct height. That is coordinate compression, and here it is not an optimisation but the thing that makes an array-indexed tree possible at all.

Three event kinds, and their order at equal x is the entire correctness argument:

x = h.xlo insert h.y type 0 x = v.x query [ylo, yhi] type 1 x = h.xhi remove h.y type 2

Sort by x, then by type. Inserting before querying makes a horizontal segment that STARTS at the sweep line count, and removing after querying makes one that ENDS at the sweep line count. Both are required, because the segments are closed: a vertical segment touching the left or right end of a horizontal one shares exactly that endpoint, and sharing a point is what is being counted. Swap either ordering and the answer is wrong only on touching configurations, which is the kind of bug that survives small tests.

## Width

With 10^5 horizontal and 10^5 vertical segments the answer can reach 10^10, which is past 2147483647 and so needs a 64-bit accumulator. The Fenwick tree's own counters stay below n, so only the total needs the wide type, and it is the total where the overflow happens: a 32 bit build silently wraps it and prints a small or negative count with no other symptom. Coordinates satisfy |x|, |y| <= 1000000, and no cross product appears in this solution at all, because every test is a comparison of coordinates.

Constraints - `1 <= n <= 200000` - `-1000000 <= x1, y1, x2, y2 <= 1000000` - every segment is axis-aligned with positive length, so exactly one of `x1 == x2` and `y1 == y2` holds - the answer can be as large as 10000000000, which is past the top of a signed 32-bit integer