「ROI 2025 Day1 T2」天狼星换班 题解

题目分析

我们有 $n$ 个房间和 $k$ 名员工，每个员工负责区间 $[l_i, r_i]$，且必须从 $m_i$ 开始工作。只有当员工到达起点 $m_i$ 时该房间还未被维修，他才会维修整个区间 $[l_i, r_i]$；否则直接返回。

我们需要判断是否存在一种员工出发顺序，使得所有房间最终都被维修。

关键观察

1. 起点决定有效性：一个员工能否发挥作用，完全取决于他到达 $m_i$ 时该房间是否已被维修。
2. 覆盖依赖关系：如果员工 $i$ 的 $m_i$ 落在员工 $j$ 的区间 $[l_j, r_j]$ 内，那么员工 $j$ 必须在员工 $i$ 之前出发，否则员工 $i$ 的 $m_i$ 可能被员工 $j$ 提前修好，导致员工 $i$ 不工作。
3. 问题转化：这实际上是一个区间覆盖问题，但带有特殊的"激活条件"。

算法思路

动态规划 + 线段树优化

我们使用动态规划求解，定义状态：

• $dp[i]$：表示能够覆盖到房间 $i$ 时，所需的最小"最大起始位置"

状态转移

对于每个右端点为 $i$ 的区间 $[l, m, i]$：

• 情况1：从左边覆盖。查询 $[l-1, m-1]$ 区间的最小 $dp$ 值 $w_1$
• 情况2：从右边覆盖（如果 $m < i$）。查询 $[m, i-1]$ 区间的最小 $dp$ 值 $w_2$，如果 $w_2 < l$ 说明可以从右边覆盖
• 取两种情况的最小值，然后更新：$dp[i] = \min(dp[i], \max(w, m))$

其中 $w$ 是上述两种情况得到的最小值。

线段树优化

使用线段树维护 $dp$ 数组的区间最小值，支持：

• 单点修改：更新 $dp[i]$
• 区间查询：快速获取区间内最小 $dp$ 值

算法步骤

1. 按右端点分组：将所有区间按 $r_i$ 分组
2. 初始化：$dp[0] = 0$，其他 $dp[i] = \infty$
3. 从左到右DP：
   • 对于每个位置 $i$，处理所有右端点为 $i$ 的区间
   • 对每个区间 $[l, m, i]$，用线段树查询计算最优解
   • 更新 $dp[i]$
4. 判断答案：如果 $dp[n] \neq \infty$，输出 YES，否则 NO

复杂度分析

• 时间复杂度：$O((n + k) \log n)$
  • 每个区间查询两次线段树：$O(\log n)$
  • 总共 $k$ 个区间：$O(k \log n)$
  • 遍历 $n$ 个位置：$O(n)$
• 空间复杂度：$O(n + k)$

总结

本题的难点在于发现区间覆盖的依赖关系，并将其转化为动态规划问题。通过巧妙的状态设计和线段树优化，我们能够在 $O((n+k)\log n)$ 的时间内解决问题。