1458. The Pairs That Only Touch

n shifts are given. Shift i is the CLOSED stretch [a, b] with a < b, so every shift has positive length.

Print how many unordered pairs of shifts share EXACTLY ONE point: they meet, but the part they share has no width.

[1,3] [3,5] [5,7] [2,9] -> 2 [1,5] [2,6] [8,9] -> 0 [1,3] [3,5] -> 1

Trace the first line. [1,3] and [3,5] share only the point 3, and [3,5] and [5,7] share only the point 5: two such pairs. [1,3] and [5,7] share nothing. [2,9] overlaps each of the first three on a stretch of positive width, so none of those three pairs counts. The answer is 2.

These are exactly the pairs on which the closed and the half-open readings disagree, which is why counting them is worth doing once explicitly.

## What most people try first

Two nested loops computing lo = max(a1, a2) and hi = min(b1, b2) and counting the pairs with lo == hi. That is correct and O(n^2): at n = 200000 it is 2 * 10^10 pair tests.

The second reflex is to sort by start and compare each shift only with the next one. That misses every pair that is not adjacent in sorted order, and there can be many: a hundred shifts all ending at 5 and a hundred all starting at 5 give ten thousand touching pairs, none of them adjacent to more than one other.

## The shared point is always an endpoint of both

Suppose two shifts share exactly the point p. Then max(a1, a2) = p and min(b1, b2) = p, so one of them starts at p and one of them ends at p. It cannot be the same one, since a shift has a < b. So a touching pair is always one shift ENDING at p paired with one shift STARTING at p:

count how many shifts start at each coordinate, in a map answer = 0 for each shift [a, b]: answer += how many shifts start at b

That is O(n) expected with a hash map, or O(n log n) with a sorted array and a binary search.

## Why the count is exact, with nothing double counted

Take a pair counted by the loop, at shift i with b_i = a_j. Then max(a_i, a_j) = a_j = b_i = min(b_i, b_j), using a_i < b_i = a_j and a_j < b_j. So the pair really does share exactly one point.

Conversely every touching pair is counted, by the argument above. And no pair is counted twice: that would need b_i = a_j AND b_j = a_i, giving a_i < b_i = a_j < b_j = a_i, which says a_i < a_i.

A shift is never counted against itself either, since a < b means its own start differs from its own end.

## The boundary that breaks a careless implementation

Two shifts with the SAME endpoints share their whole width, not a point, so they must not be counted. The rule above handles that automatically: identical shifts have the same b, which is strictly larger than the a they share, so neither is counted against the other. What does go wrong is a solution that counts every coordinate appearing as both an endpoint and a start without checking which shift it came from.

If the constraint were a <= b rather than a < b, a zero-width shift would start and end at the same point and would be counted against itself. The strict constraint is what makes the one-line rule safe.

## Overflow

With 10^5 shifts ending at one coordinate and 10^5 starting there the answer is 10^10, well past the 2147483647 a signed 32 bit integer holds, so the counter must be 64 bit. The coordinates themselves reach only 10^9 and fit comfortably.

## Related

Problem 1456 counts every pair that shares at least one point, of which these are the borderline cases; subtracting one from the other gives the pairs that overlap with positive width. Problem 1457 asks the same question about a single pair and prints the two conventions' answers side by side.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9`, so every shift has positive length - each shift is the closed stretch `[a, b]`, so both endpoints belong to it - two shifts count only when the part they share is a single point