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

题目分析

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

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

关键观察

1. 激活条件：员工 $i$ 能够工作的充要条件是：在它出发时，房间 $m_i$ 尚未被维修
2. 覆盖依赖：如果员工 $i$ 的 $m_i$ 落在员工 $j$ 的区间内，那么员工 $j$ 必须在员工 $i$ 之前出发
3. 问题转化：这实际上是一个带特殊约束的区间覆盖问题

算法思路

动态规划 + 线段树优化

我们使用动态规划来求解这个问题：

状态定义

设 $dp[i]$ 表示能够覆盖到房间 $i$ 所需的最小条件（具体是最小的某个值）

状态转移

对于每个员工 $[l, m, r]$：

• 情况1：查询区间 $[l-1, m-1]$ 的最小 $dp$ 值
• 情况2：查询区间 $[l-1, r]$ 的最小 $dp$ 值
• 如果满足某种条件，则更新 $dp[r] = \min(dp[r], m)$

线段树优化

使用线段树维护 $dp$ 数组，支持：

• 区间最小值查询
• 单点更新（取最小值）

算法步骤

1. 输入处理：读入所有员工信息 $[l_i, m_i, r_i]$
2. 排序：按 $m_i$ 对员工排序
3. 初始化：线段树初始化为无穷大，$dp[0] = 0$
4. 处理每个员工：

   for (auto &&[p, l, r] : a) {
       int t1 = ask(l-1, p-1);  // 查询区间 [l-1, m-1]
       int t2 = ask(l-1, r);    // 查询区间 [l-1, r]
       
       if (t1 < p || t2 < l)    // 满足激活条件
           modify(r, p);         // 更新 dp[r]
   }
   

5. 判断答案：检查 $dp[n]$ 是否被更新过

复杂度分析

• 时间复杂度：$O(k \log n)$
  • 排序：$O(k \log k)$
  • 每个员工两次线段树查询 + 一次更新：$O(\log n)$
• 空间复杂度：$O(n + k)$

算法正确性

该算法的核心在于：

1. 按 $m_i$ 排序：确保处理顺序合理，避免循环依赖
2. 条件检查：通过查询历史 $dp$ 值判断当前员工能否被激活
3. 贪心更新：一旦员工能被激活，就更新其能覆盖的右端点

当 $dp[n]$ 被成功更新时，说明存在一种顺序可以覆盖所有房间。

代码实现要点

// 线段树维护区间最小值
void modify(int p, int x) {
    for (p += tm; p; p >>= 1)
        tr[p] = min(tr[p], x);
}

int ask(int l, int r) {
    // 标准线段树区间查询
}

// 主算法
for (auto &&[p, l, r] : a) {
    int t1 = ask(l-1, p-1);
    int t2 = ask(l-1, r);
    
    if (t1 < p || t2 < l)
        modify(r, p);
}

总结

本题通过巧妙的动态规划状态设计和线段树优化，将复杂的顺序依赖问题转化为区间查询和更新问题。算法在 $O(k \log n)$ 的时间内解决了问题，能够处理大规模数据输入。

算法标签：线段树 动态规划 区间覆盖 贪心算法 离线处理