题解

题目描述

给定 $n$ 个区间，每个区间表示为 $[l_i, r_i]$，计算有多少对不同的区间满足这两个区间有交集。

思路分析

这道题要求计算所有区间对中有交集的数目，我们可以将其转化为总对数减去不相交的对数。具体做法是：首先将所有区间按左端点升序排序，然后利用离散化和树状数组高效统计每个区间之前有多少区间的右端点小于当前区间的左端点（即不相交的情况），最后用组合数公式计算总对数并减去不相交对数得到答案。

题目内容

对于给定的$n$个区间，我们使用一个二元组{$l_i.,r_i$}来描述第$i$个区间覆盖$[l_i,r_i]$(包含端点)。

现在，请计算有多少对不同的区间$[l_u,r_u]$和$[l_v,r_v](u≠v)$使得这两个区间有交集，即满足

$min(r_u,r_e)≥max(l_u,l_v,)$

输入描述

第一行输入一个整数$n(1≦n≦10^5)$代表给定的区间数量。

此后$n$行,第$i$行输入两个整数

$l_i,r_i(0≦l_i≦r_i≦10^9)$代表第$i$个区间的左右端点。

输出描述

输出一个整数，表示满足条件的区间对的数量。

样例1

输入

5
1 3
2 4
5 7
6 8
1 2

输出

4

说明

在这个样例中，满足条件的区间对有:

• 第一、二对 ([$1,3$]和[$2,4$]);
• 第一、五对([$1,3$]和[$1,2$]);
• 第二、五对([$2,4$]和[$1,2$]);
• 第三、四对 ([$5,7$]和[$6,8$]);

因此，输出结果为$4$。