CF137C History

Polycarpus 非常喜欢在学校学习，并且总是认真完成作业。Polycarpus 在自然科学方面从未遇到过任何问题，因为他的曾曾祖父是著名物理学家 Seinstein。然而，Polycarpus 在历史方面却一直不太顺利。 众所周知，世界历史恰好包含 $n$ 个事件：第 $i$ 个事件从 $a_{i}$ 年持续到 $b_{i}$ 年（包含 $a_{i}$ 和 $b_{i}$，且 $a_{i} < b_{i}$）。Polycarpus 很容易记住每个事件的开始和结束年份（他从曾曾祖父那里继承了极好的记忆力）。但老师给了他一个更复杂的任务：Polycarpus 需要知道所有事件的起止时间，并且还要判断每个事件是否被另一个事件包含。Polycarpus 的老师认为，如果 $a_{j} < a_{i}$ 且 $b_{i} < b_{j}$，则事件 $j$ 包含事件 $i$。你的任务更简单：只需计算有多少个事件被其他某个事件包含。

第一行包含一个整数 $n$（$1 \leq n \leq 10^{5}$），表示事件的数量。接下来的 $n$ 行，每行描述一个历史事件。第 $i+1$ 行包含两个整数 $a_{i}$ 和 $b_{i}$（$1 \leq a_{i} < b_{i} \leq 10^{9}$），分别表示第 $i$ 个事件的开始和结束年份。没有两个事件在同一年开始或结束，即对于所有 $i \neq j$，都有 $a_{i} \neq a_{j}$，$a_{i} \neq b_{j}$，$b_{i} \neq a_{j}$，$b_{i} \neq b_{j}$。事件的顺序是任意的。

输出一个整数，表示被其他某个事件包含的事件数量。

在第一个样例中，第五个事件被第四个事件包含。类似地，第四个事件被第三个事件包含，第三个事件被第二个事件包含，第二个事件被第一个事件包含。 在第二个样例中，除了第一个事件外，其余所有事件都被第一个事件包含。 在第三个样例中，只有一个事件，所以答案是 $0$。 由 ChatGPT 4.1 翻译