#73. 二维偏序

二维偏序

问题描述

给定 nn 个二元组 (xi,yi)(x_i,y_i),求解满足 (xixjyiyj)(x_i\le x_j \land y_i\le y_j)的索引对数量,(i,j)(i, j)(j,i)(j, i) 视为相同的索引对,(i,i)(i, i) 不视为索引对。

输入格式

第一行输入一个正整数 nn(2n2×105)(2\le n\le 2\times 10^5)

接下来 nn 行,每行输入两个正整数,表示 (xi,yi)(x_i,y_i)(1xi,yi109)(1\le x_i,y_i\le 10^9)

输出格式

输出符合题目要求的索引对数量。

样例输入1

4
1 1
1 3
2 3
3 2

样例输出1

4

样例输入2

4
4 4
1 1
1 1
3 2

样例输出2

6

说明

图片描述

样例 1 如上图所示。