‹ 上一题下一题 ›

j00906. 二维偏序计数未做

1000 ms 256 MB 测试点 5 J-25·排序 J·算法自拟题排序算法

文件读写输入j00906.in输出j00906.out

题目描述

平面上 $n$ 个点，统计满足 $i < j$ 、 $x_{j} > x_{i}$ 且 $y_{j} < y_{i}$ 的点对个数。

输入格式

第一行一个正整数 $n$ ；接下来 $n$ 行每行两个整数 $x_{i}, y_{i}$ 。

输出格式

一行一个整数。

样例

输入

输出

数据范围

$1 \leq n \leq 1 0^{5}$ ， $∣ x_{i} ∣, ∣ y_{i} ∣ \leq 1 0^{9}$ （正解：排序一维 + 树状数维护另一维）

输入

输出

答案