求包含给定子区间集合中至少一个区间的[a,b]子区间总数

核心采用补集思想：先计算闭区间[a,b]内所有子区间的总数，再减去不包含S中任何区间的子区间数量，最终得到集合C的大小。

步骤分解 #

1. 计算总子区间数 #

[a,b]内的闭子区间总数可通过公式直接计算：

total = (b - a + 1) * (b - a + 2) // 2

推导：长度为k的区间共有(b - a + 1 - k + 1)个，对k从1到b-a+1求和，本质是等差数列求和。

2. 计算补集（不包含任何S中区间的子区间数） #

补集的定义是：子区间[c,d]满足对所有i∈[1,n]，[l_i,r_i]都不被[c,d]包含，等价于对每个i，要么c > l_i，要么r_i > d。

我们通过固定右端点d，计算每个d对应的合法左端点c的数量，累加后得到补集大小：

预处理

• 将S中的区间按右端点r_i从小到大排序，时间复杂度O(n log n)。
• 用双指针维护当前所有r_i ≤ d的区间中左端点l_i的最大值：初始化指针p=0，当前最大l_i设为L = a-1（表示无符合条件的区间时，所有c均合法）。

基础遍历计算（适用于b-a较小时）

遍历d从a到b：

• 若p < n且S[p].r ≤ d，则更新L = max(L, S[p].l)，并将指针p右移。
• 当前d对应的合法c数量为max(0, d - L)（c的取值范围是(L, d]，共d - L个值）。
• 累加所有d的合法c数量，得到补集大小complement。

离散化优化（适用于b-a极大时）

若b-a是极大值（如1e9），无法逐个遍历d，可通过离散化处理：

• 收集所有关键节点：a、b、所有r_i，排序去重得到序列x_0=a, x_1, x_2,...,x_k=b。
• 对每个相邻节点构成的区间[x_p, x_{p+1}-1]：
  • 该区间内所有d对应的L是固定值（已通过双指针预处理得到）。
  • 计算区间内d的数量：cnt = x_{p+1} - x_p。
  • 该区间内合法c的总数为：(x_p + x_{p+1} - 1) * cnt // 2 - L * cnt（等差数列求和减去L乘以区间长度）。
• 累加所有区间的结果得到complement。

3. 计算集合C的大小 #

最终结果为总子区间数减去补集大小：

m = total - complement

时间复杂度 #

• 基础版本：O(n log n + l)，其中l = b-a。
• 离散化版本：O(n log n)，适合l极大的场景。

该方法相比原朴素解法的O(l²n)，效率提升显著，尤其在l或n较大时优势明显。

内容的提问来源于stack exchange，提问作者BallStretcher257