📏 线段相交

📘 题目描述

给定平面上的 n 条水平线段，每条线段由起点 l 和终点 r 表示，满足 l < r。

请你计算一共有多少对线段是相交的（即两个线段有公共区间）。

📥 输入格式

• 第一行一个整数 n（1 ≤ n ≤ 100000），表示线段数量；
• 接下来的 n 行，每行两个整数 l 和 r（1 ≤ l < r ≤ 100000），表示一条线段的起点和终点。

📤 输出格式

• 输出一个整数，表示有多少对线段相交。

📌 输入样例

4
1 3
2 5
4 6
7 8

📌 输出样例

2

🧠 解题思路

线段 [l1, r1] 和 [l2, r2] 相交的条件：

$\max(l1, l2) < \min(r1, r2)$即它们有公共部分。

高效做法（扫描线 + 有序集合）

1. 将所有线段按 l 升序排序；
2. 遍历每个线段 (l, r)，统计当前所有 r' ≥ l 的线段数；
3. 使用 multiset 或线段树维护当前活跃线段的右端点；
4. 每次插入一个 r 前，先移除所有 r' < l 的线段。