Tokitsukaze and Strange Rectangle
Contest: Codeforces Round 573 (Div. 1)
Difficulty rating: 2000
Tags: data structures, divide and conquer, sortings, two pointers

There are $$$n$$$ points on the plane, the $$$i$$$-th of which is at $$$(x_i, y_i)$$$. Tokitsukaze wants to draw a strange rectangular area and pick all the points in the area.

The strange area is enclosed by three lines, $$$x = l$$$, $$$y = a$$$ and $$$x = r$$$, as its left side, its bottom side and its right side respectively, where $$$l$$$, $$$r$$$ and $$$a$$$ can be any real numbers satisfying that $$$l < r$$$. The upper side of the area is boundless, which you can regard as a line parallel to the $$$x$$$-axis at infinity. The following figure shows a strange rectangular area.

A point $$$(x_i, y_i)$$$ is in the strange rectangular area if and only if $$$l < x_i < r$$$ and $$$y_i > a$$$. For example, in the above figure, $$$p_1$$$ is in the area while $$$p_2$$$ is not.

Tokitsukaze wants to know how many different non-empty sets she can obtain by picking all the points in a strange rectangular area, where we think two sets are different if there exists at least one point in one set of them but not in the other.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$) — the number of points on the plane.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th point.

All points are distinct.

Output format:
Print a single integer — the number of different non-empty sets of points she can obtain.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
For the first example, there is exactly one set having $$$k$$$ points for $$$k = 1, 2, 3$$$, so the total number is $$$3$$$.

For the second example, the numbers of sets having $$$k$$$ points for $$$k = 1, 2, 3$$$ are $$$3$$$, $$$2$$$, $$$1$$$ respectively, and their sum is $$$6$$$.

For the third example, as the following figure shows, there are

- $$$2$$$ sets having one point;
- $$$3$$$ sets having two points;
- $$$1$$$ set having four points.

Therefore, the number of different non-empty sets in this example is $$$2 + 3 + 0 + 1 = 6$$$.

Example input:
3
1 1
1 2
1 3

Example output:
3

Example input:
3
1 1
2 1
3 1

Example output:
6

Editorial:
For each strange rectangular area and its corresponding set of points, we only need to focus on the lowest $$$y$$$-coordinate $$$yB$$$, the leftmost $$$x$$$-coordinate $$$xL$$$ and the rightmost $$$x$$$-coordinate $$$xR$$$ of points in this set. Different sets must have different $$$yB$$$, $$$xL$$$, $$$xR$$$, so we can count them by enumerating these values.
Let's enumerate $$$yB$$$ first. Then, we need to list all the possible $$$x$$$-coordinates of points $$$(x_i, y_i)$$$ satisfying that $$$y_i \geq yB$$$ and mark every possible $$$x'$$$ satisfying there is a point $$$(x', yB)$$$. By doing so, we can make sure when enumerating $$$xL$$$ and $$$xR$$$, the requirement for $$$yB$$$ is met as well. However, enumerating forcibly, which is in time complexity $$$\mathcal{O}(n^3)$$$, is too slow to pass, so let's optimize the enumeration step by step.
Let's pick and sort the points $$$(x'_1, yB), (x'_2, yB), \ldots, (x'_m, yB)$$$ from left to right. Assuming that $$$x'_0 = 0$$$, and $$$(x'_j, yB)$$$ is the leftmost point of them that is in the chosen set, we can count the number of aforementioned different $$$x$$$-coordinates in ranges $$$[x'_{j - 1} + 1, x'_j]$$$ and $$$[x'_j, \infty)$$$ and then count the number of possible pairs $$$(xL, xR)$$$ immediately. More specifically, let $$$cnt(l, r)$$$ be the number of different $$$x$$$-coordinates of points in the area $$$\lbrace (x, y) | l \leq x \leq r, y \geq yB \rbrace$$$, and we know the number of possible pairs $$$(xL, xR)$$$ is $$$cnt(x'_{j - 1} + 1, x'_j) \cdot cnt(x'_j, \infty)$$$. After precalculating $$$c(1, x)$$$ for each $$$yB$$$, we can reduce the time complexity into $$$\mathcal{O}(n^2)$$$.
The very last step is using the trick of sweeping lines. We can enumerate $$$yB$$$ from highest to lowest, and during that process, use data structures to maintain possible $$$x$$$-coordinates. What we need to implement is to maintain a container, check if a coordinate is already in the container, add a coordinate to the container, and query the number of coordinates in a range. These requirements can be easily achieved by Fenwick tree, segment tree or others. With the last optimization, we can solve in time complexity $$$\mathcal{O}(n \log n)$$$.