D. 区间的区间 详细题解

问题重述

给定 $n$ 个区间 $[a_i, b_i]$，定义区间之区间 $[l, r]$（$1 \le l \le r \le n$）的价值为第 $l$ 到第 $r$ 个区间的并集长度。需要选择恰好 $k$ 个不同的区间之区间，使得它们的价值和最大，求这个最大值。

关键观察

观察 1：区间之区间价值的计算

对于固定的右端点 $r$，考虑所有左端点 $l$（$1 \le l \le r$）对应的价值 $val(l, r)$。

当处理到第 $r$ 个区间时，我们可以维护数轴上每个位置最后被覆盖的时间戳（即最后一次覆盖该位置的区间编号）。那么：

$$val(l, r) = \text{时间戳} \ge l \text{ 的位置数量}$$

因为一个位置对 $val(l, r)$ 有贡献当且仅当它在 $l$ 到 $r$ 之间至少被覆盖一次。

观察 2：时间戳的更新

当我们加入新区间 $[a_r, b_r]$ 时，需要将区间 $[a_r, b_r]$ 内所有位置的时间戳更新为 $r$。如果这些位置之前的时间戳是 $r'$，那么对于所有 $l \in [r'+1, r]$，$val(l, r)$ 都会增加 $1$（因为这些位置现在被覆盖了）。

观察 3：用线段维护相同时间戳的区间

由于时间戳相同的连续位置可以合并成一段，我们可以使用平衡树（如 std::set）来维护这些段。每段表示为 $(位置起点, 时间戳)$。

当加入新区间 $[l, r]$ 时：

1. 找到与 $[l, r]$ 相交的所有段
2. 对于每个被完全覆盖的段，它会被删除，并触发对应的区间加操作
3. 对于部分覆盖的段，需要分割
4. 最后插入新的段 $(l, r)$，时间戳为 $i$

总操作次数为 $O(n)$，因为每个段最多被创建和删除一次。

观察 4：选择最大的 $k$ 个值

我们需要从所有 $\frac{n(n+1)}{2}$ 个区间之区间中选出最大的 $k$ 个。可以使用二分答案：

设 $x$ 为选中的最小值，我们需要：

• 统计价值 $\ge x$ 的区间之区间数量 $cnt$
• 计算这些区间的价值和 $sum$

如果 $cnt \ge k$，说明可以选更大的 $x$；否则需要减小 $x$。

最终答案 = $sum - (cnt - k) \times x$（减去多余的部分）。

观察 5：快速统计 $\ge x$ 的区间

对于固定的 $x$，我们可以用滑动窗口计算：

对于每个右端点 $i$，定义 $L_i$ 为最小的左端点，使得 $val(L_i, i) \ge x$。由于 $val(l, i)$ 随 $l$ 增加而减小，所有 $l \le L_i$ 都满足条件。

维护：

• t1：当前窗口内所有 $val(l, i)$ 的和
• t2：当前窗口内覆盖的位置总数

当 $i$ 增加到 $i+1$ 时，需要：

1. 更新时间戳，可能增加 $t1$ 和 $t2$
2. 移动左边界 $j$，使 $t2 \ge x$
3. 更新统计量

算法步骤

第一部分：预处理每个 $i$ 的时间戳变化

对于每个 $i$，记录当加入区间 $i$ 时，所有被覆盖段的时间戳变化：

• 每个变化表示为 (timestamp, length)，表示有一段时间戳为 timestamp 的长度为 length 的段被覆盖

这些变化用于在二分答案时快速更新统计量。

第二部分：二分答案

二分价值阈值 $x$：

1. 初始化：

   • j = 1（窗口左边界）
   • t1 = 0（当前窗口内所有 $val(l, i)$ 的和）
   • t2 = 0（当前窗口内覆盖的位置总数）
   • s1 = 0（所有 $\ge x$ 的区间价值和）
   • s2 = 0（所有 $\ge x$ 的区间数量）

2. 对于 $i = 1$ 到 $n$：

   • 应用第 $i$ 个区间的所有变化（来自预处理）
   • 移动左边界 $j$，使 $t2 \ge x$
   • 更新 $s1$ 和 $s2$

3. 根据 $s2$ 与 $k$ 的比较调整二分边界

第三步：计算答案

最终答案 = $S1 - (S2 - k) \times X$，其中 $X$ 是二分找到的阈值。

时间复杂度

• 预处理：$O(n)$（每个段最多被处理一次）
• 二分答案：$O(\log(10^9) \cdot n)$
• 总复杂度：$O(n \log(\text{值域}))$

完整代码实现

#include<bits/stdc++.h>
using namespace std;

const int MN = 300000;
const int MAX_POS = 1e9;

set<pair<int, int>> st;  // (位置, 时间戳)
vector<pair<int, int>> v[MN + 5];  // v[i]: 当加入区间 i 时的时间戳变化
int f[MN + 5];  // 辅助数组，记录每个时间戳对应的长度

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    
    // 初始化：整个数轴时间戳为 0
    st.insert({1, 0});
    st.insert({MAX_POS, 0});
    
    for (int i = 1; i <= n; ++i) {
        int l, r;
        scanf("%d%d", &l, &r);
        
        // 找到第一个位置 >= l 的段
        auto it = st.upper_bound({l, n});
        auto tt = it;
        --tt;  // tt 是前一个段
        
        // 处理左边界部分覆盖
        int x = tt->second;  // 前一段的时间戳
        v[i].push_back({x, tt->first - l});  // 左边被覆盖的部分
        
        if (tt->first < l) {
            // 部分覆盖，需要保留左边部分
            v[i].push_back({x, l - tt->first});
        } else {
            // 完全覆盖，删除整个段
            st.erase(tt);
        }
        
        // 插入新区间
        v[i].push_back({i, r - l});
        st.insert({l, i});
        
        // 处理中间完全覆盖的段
        while (tt->first < r) {
            it = tt;
            ++tt;
            x = it->second;
            v[i].push_back({x, it->first - tt->first});
            st.erase(it);
        }
        
        // 处理右边界部分覆盖
        if (tt->first > r) {
            x = tt->second;
            v[i].push_back({x, tt->first - r});
            st.insert({r, x});
        }
    }
    
    // 二分答案
    int L = 1, R = 1e9, X = 0;
    long long S1 = 0, S2 = 0;
    
    while (L <= R) {
        int x = (L + R) / 2;
        
        memset(f, 0, sizeof(f));
        long long s1 = 0, s2 = 0;  // 总价值和，总数量
        long long t1 = 0, t2 = 0;  // 当前窗口的和，当前窗口的覆盖长度
        int j = 1;  // 窗口左边界
        
        for (int i = 1; i <= n; ++i) {
            // 应用第 i 个区间的所有变化
            for (auto [timestamp, len] : v[i]) {
                if (timestamp < j) {
                    t1 += 1LL * timestamp * len;
                } else {
                    t1 += 1LL * (j - 1) * len;
                    t2 += len;
                    f[timestamp] += len;
                }
            }
            
            // 移动左边界，使 t2 >= x
            while (j <= i && t2 >= x) {
                t1 += t2;
                t2 -= f[j];
                ++j;
            }
            
            s1 += t1;
            s2 += j - 1;
        }
        
        if (s2 >= m) {
            X = x;
            S1 = s1;
            S2 = s2;
            L = x + 1;
        } else {
            R = x - 1;
        }
    }
    
    // 计算答案：减去多余的部分
    printf("%lld\n", S1 - (S2 - m) * X);
    
    return 0;
}

代码说明

1. 数据结构：

   • st：维护数轴上的段，每个段有起点和时间戳
   • v[i]：记录加入区间 $i$ 时的时间戳变化，每个变化为 (时间戳, 长度)

2. 预处理过程：

   • 使用 set 维护所有段
   • 当新区间覆盖某个段时，记录该段被覆盖，并更新统计
   • 每个段最多被创建和删除一次，总操作 $O(n)$

3. 二分答案过程：

   • f[timestamp]：记录当前窗口内每个时间戳对应的总长度
   • t1：当前窗口内所有 $val(l, i)$ 的和
   • t2：当前窗口内覆盖的总长度
   • 滑动窗口维护左边界，使 $t2 \ge x$

4. 边界处理：

   • 时间戳为 $0$ 表示从未被覆盖
   • 窗口左边界 $j$ 从 $1$ 开始
   • 当 $t2 < x$ 时，不能移动左边界

示例演示

以第二个样例为例：

3 3
1 4
5 7
3 6

处理过程：

1. 加入区间1 $[1,4]$：覆盖位置1-4，时间戳=1
2. 加入区间2 $[5,7]$：覆盖位置5-7，时间戳=2
3. 加入区间3 $[3,6]$：覆盖位置3-6，时间戳=3
   • 位置3-4原来时间戳=1，变为3
   • 位置5-6原来时间戳=2，变为3

最终统计所有区间之区间的价值：

• $[1,1]=3$, $[1,2]=5$, $[1,3]=6$
• $[2,2]=2$, $[2,3]=4$
• $[3,3]=3$

选择最大的3个：6+5+4=15

总结

本题的核心技巧：

1. 用时间戳表示每个位置最后被覆盖的时间
2. 用平衡树维护相同时间戳的连续段
3. 通过预处理记录每次更新对答案的贡献
4. 二分答案 + 滑动窗口统计价值 $\ge x$ 的区间数量和
5. 最终答案 = 总价值和 - (超出数量) × 阈值