题目内容

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

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

题解

题目描述

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

思路分析

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