题解：疫情传播与区间覆盖的动态规划最优化

---

问题分析

本题要求选择若干治疗方案，使得最终所有居民都被治愈。病毒的传播具有相邻传染性，治疗方案有执行时间、覆盖区间和代价。需要找到满足条件的最小总代价方案，或判断无解。

关键约束：

• 病毒每天向相邻房屋传播
• 治疗方案在特定时间晚上执行，治愈覆盖区间内的感染者
• 已治愈的居民可能再次被感染
• 方案可以多天同时执行

---

关键观察与转化

1. 方案之间的依赖关系

考虑两个治疗方案 $i$ 和 $j$（$T_i < T_j$）。要使方案 $j$ 能有效治愈居民，需要确保在时间 $T_j$ 之前，病毒不会从方案 $i$ 的覆盖区间外传播到 $j$ 的覆盖区间内。

更具体地：

• 设方案 $i$ 覆盖 $[L_i, R_i]$，在 $T_i$ 执行
• 方案 $j$ 覆盖 $[L_j, R_j]$，在 $T_j$ 执行
• 如果 $L_j \le R_i + (T_j - T_i)$，那么病毒可能从右侧传播进来
• 如果 $R_j \ge L_i - (T_j - T_i)$，那么病毒可能从左侧传播进来

实际上，方案 $j$ 能接续方案 $i$ 的条件是它们的覆盖区间在考虑时间差后能够"连接"起来。

2. 转化为图论问题

将每个治疗方案视为图中的一个节点，从节点 $i$ 到节点 $j$ 连有向边当且仅当：

• $T_i < T_j$
• $L_j \le R_i + T_j - T_i$（右侧连接）
• $R_j \ge L_i - (T_j - T_i)$（左侧连接）

边的权重为方案 $j$ 的代价 $C_j$。问题转化为：找到从覆盖起始点（左端点为1）到覆盖终点（右端点为N）的最小代价路径。

3. 进一步优化

直接建图边数可能达到 $O(M^2)$，不可行。需要利用数据结构优化边的查找。

---

算法框架

第一步：排序与预处理

1. 将所有治疗方案按时间 $T$ 排序
2. 定义两个关键值：
   • $A_i = L_i - T_i$（左侧传播相关）
   • $B_i = L_i + T_i$（右侧传播相关）

第二步：线段树优化建图

维护两棵线段树（或同一棵树维护两个值）：

• MinA：维护 $L_i - T_i$ 的最小值
• MinB：维护 $L_i + T_i$ 的最小值

对于当前处理的方案 $u$：

1. 查找左侧可连接方案： 对于时间在 $u$ 之前的方案 $v$（$T_v < T_u$），如果 $L_u \le R_v + T_u - T_v$，即 $L_u - T_u \le R_v - T_v$，则 $v$ 可以连接到 $u$。

   我们查询满足 $A_v \le R_u - T_u$ 的方案。

2. 查找右侧可连接方案： 对于时间在 $u$ 之后的方案 $v$（$T_v > T_u$），如果 $L_v \le R_u + T_v - T_u$，即 $L_v + T_v \le R_u + T_u$，则 $u$ 可以连接到 $v$。

   我们查询满足 $B_v \le R_u + T_u$ 的方案。

第三步：Dijkstra算法求最短路

1. 初始化：对于覆盖左端点（$L=0$）的方案，$f[i] = C_i$，加入优先队列
2. 每次取出当前代价最小的方案 $u$
3. 查询所有能与 $u$ 连接的方案 $v$
4. 如果 $f[v] > f[u] + C_v$，更新 $f[v]$ 并加入优先队列
5. 最终答案为覆盖右端点（$R=N$）的方案中的最小 $f$ 值

第四步：判断无解

如果没有方案能覆盖到右端点 $N$，则输出 $-1$。

---

正确性证明

1. 连接条件的完备性
   基于病毒传播的特性，两个方案能有效衔接的条件已完全转化为不等式条件。

2. 最短路模型的正确性
   每个治疗方案的选择相当于图中的一条路径，总代价为路径上所有节点代价之和。Dijkstra算法能找到最小代价路径。

3. 数据结构优化的正确性
   线段树维护的关键值 $A_i$ 和 $B_i$ 将二维条件（时间和位置）转化为一维查询，确保了查询的高效性。

---

复杂度分析

• 时间复杂度：$O(M\log M)$
  • 排序：$O(M\log M)$
  • 每个方案最多被加入队列一次，每次查询 $O(\log M)$
  • 总复杂度 $O(M\log M)$
• 空间复杂度：$O(M)$

对于 $M \le 10^5$ 的数据范围完全可行。

---

总结

本题是一道结合区间覆盖与时间依赖的动态规划最优化问题，主要考察：

1. 问题建模能力：将病毒传播和治疗方案转化为图论中的最短路问题
2. 不等式转化技巧：将复杂的传播条件简化为可处理的不等式
3. 数据结构优化：使用线段树将二维查询优化为一维
4. Dijkstra算法应用：在动态更新的图上求最短路

算法的核心在于：

• 识别治疗方案之间的可连接条件
• 通过巧妙的变量代换（$A_i = L_i - T_i$, $B_i = L_i + T_i$）将二维条件线性化
• 使用线段树快速查询可连接的方案

这种"时间+空间"的二维优化问题在竞赛中较为常见，但本题的病毒传播机制和治愈后可能再感染的特点增加了问题的复杂性，需要仔细分析才能得到正确的转化方法。