题目分析

本题需要处理多个区间对，每个区间对包含两个区间。我们需要从每个区间对中选择一个区间，使得所有被选中的区间的并集覆盖的总长度最大化。

算法思路

核心思想

1. 离散化处理：将区间端点映射到较小的范围内，便于处理

2. 差分数组：高效标记区间覆盖情况

3. 前缀和/后缀和：快速计算区间覆盖的统计信息

4. 贪心策略：通过比较不同选择的覆盖范围，确定最优解

算法标签

离散化 (Discretization)

差分数组 (Difference Array)

前缀和 (Prefix Sum)

贪心算法 (Greedy Algorithm)

区间处理 (Interval Processing)

代码解析

1. 数据读取与预处理

void read(long long &x) {
    // 快速读取整数
}

• 使用快速读取函数提高输入效率

2. 离散化处理

// 收集所有区间端点
for (i = 1; i <= n; i++) {
    x[i * 2 + 1] = l2[i];
    x[i * 2 + 2] = r2[i] + 1;
}
x[1] = 1;
x[2] = 1000000001;

// 排序并离散化
sort(1, n * 2 + 2);
for (i = 1; i <= n * 2 + 2; i++) {
    if (x[num[i]] != x[num[i - 1]]) {
        to[num[i]] = to[num[i - 1]] + 1;
        q[to[num[i - 1]]] = x[num[i]] - x[num[i - 1]];
    } else
        to[num[i]] = to[num[i - 1]];
}

• 将所有区间端点收集到数组 x 中

• 对端点进行排序和去重

• 建立映射关系，将原始坐标映射到连续的整数索引

• 记录每个离散化区间段的实际长度

3. 差分数组构建

for (i = 1; i <= n; i++) {
    lmax[to[i * 2 + 2]] = lmax[to[i * 2 + 2]] + r1[i];
    lmin[to[i * 2 + 2]] = lmin[to[i * 2 + 2]] + l1[i];
    rmax[to[i * 2 + 1] - 1] = rmax[to[i * 2 + 1] - 1] + r1[i];
    rmin[to[i * 2 + 1] - 1] = rmin[to[i * 2 + 1] - 1] + l1[i];
    num[to[i * 2 + 1]] = num[to[i * 2 + 1]] + r1[i];
    num[to[i * 2 + 2]] = num[to[i * 2 + 2]] - r1[i];
}

• 使用差分数组标记区间覆盖情况

• lmax、lmin、rmax、rmin 分别记录左右边界的最大最小值信息

• num 数组记录区间覆盖的差分信息

4. 前缀和与后缀和计算

// 前缀和
for (i = 1; i <= 2 * n + 3; i++) {
    lmax[i] = lmax[i - 1] + lmax[i];
    lmin[i] = lmin[i - 1] + lmin[i];
    num[i] = num[i - 1] + num[i];
}

// 后缀和
for (i = 2 * n + 2; i >= 0; i--) {
    rmax[i] = rmax[i + 1] + rmax[i];
    rmin[i] = rmin[i + 1] + rmin[i];
}

• 通过前缀和将差分数组转换为实际的覆盖统计

• 计算从左到右和从右到左的累积信息

5. 结果计算

for (i = 1; i <= 2 * n + 2; i++) {
    if (num[i] > 0 && lmax[i] + num[i] >= rmin[i] && num[i] + rmax[i] > lmin[i]) {
        ans = ans + q[i];
    }
}

• 遍历所有离散化后的区间段

• 根据覆盖条件和边界条件判断该区间段是否应该被计入答案

• 累加符合条件的区间段长度

复杂度分析

• 时间复杂度：O(n log n)，主要开销在排序操作

• 空间复杂度：O(n)，用于存储各种数组

关键点

1. 离散化技巧：将大范围坐标映射到小范围，降低处理复杂度

2. 差分数组：高效处理区间覆盖问题

3. 贪心选择：通过比较不同选择的覆盖效果，确定最优解

该算法通过巧妙的离散化和差分技术，有效地解决了大规模区间选择与覆盖问题。