一、题意理解

1. 模型抽象

• 有 $n$ 个服务器排成链 $1-2-\dots-n$。
• 服务器 $i$ 有缓存时间 $t_i$：从它收到补丁开始，会把补丁保留 $t_i$ 秒，之后删除。
• 边 $i$（连接 $i$ 与 $i+1$）有通信时间窗口 $[l_i, r_i]$，只能在此时段内传输数据（传输瞬间完成）。
• 传输规则：如果 $A$ 有补丁（在缓存中）且 $B$ 没有，且 $A$ 与 $B$ 之间的边正在通信窗口中，则 $A$ 立即传给 $B$。
• 我们可以选择初始服务器 $j$ 收到补丁的时间 $T_j$。
• 问：对于每个 $j$，最小的 $T_j$ 使得最终所有服务器都能安装补丁。如果不可能，输出 $-1$。

关键：补丁传播是双向的，且依赖于缓存时间与通信窗口的交集。

---

二、思路分析

1. 传播约束

考虑从 $j$ 向两边传播的情况。

对于左侧传播（从 $i$ 传到 $i-1$）：

• 边 $i-1$ 的窗口是 $[l_{i-1}, r_{i-1}]$。
• 补丁到达 $i$ 的时间是某个时刻 $x$（从 $j$ 一路传过来所花的时间）。
• 为了传到 $i-1$，需要 $x$ 在 $i$ 的缓存期内与 $[l_{i-1}, r_{i-1}]$ 有交集。
• 即：存在 $y \in [l_{i-1}, r_{i-1}]$ 使得 $y \geq x$ 且 $y \leq x + t_i$。

等价于：

$$x \leq r_{i-1} \quad\text{且}\quad x \geq l_{i-1} - t_i $$

同时 $x$ 本身必须在 $[l_{i-1}, r_{i-1}]$ 与 $[x, x+t_i]$ 的交集非空，这实际上就是上面两个条件。

因此，对于固定的 $x$（到达 $i$ 的时间），能向左传的条件是：

$$l_{i-1} - t_i \leq x \leq r_{i-1}$$

---

2. 动态传播区间

设 $fl[i]$ 表示：补丁到达 $i$ 的时间 $x$ 的范围，使得从 $i$ 能向左传播到 $1$ 号服务器（如果 $i$ 在左边则向右传播的定义类似）。

我们从 1 到 n 递推 $fl[i]$：

• $fl[1] = [0, \infty]$ 表示 1 号服务器作为最左端，任何时间收到补丁都能“传到左边”（左边没服务器，自然成功）。
• 对于 $i > 1$：
  • 已知 $fl[i-1]$ 是补丁到达 $i-1$ 的时间范围，使得能继续向左传到 1。
  • 从 $i$ 传到 $i-1$ 的条件是：到达 $i$ 的时间 $x$ 满足 $l_{i-1} - t_i \leq x \leq r_{i-1}$。
  • 同时，从 $i$ 传到 $i-1$ 后，$i-1$ 收到补丁的时间就是 $y = \max(x, l_{i-1})$（因为如果 $x < l_{i-1}$，要等到窗口开启才能传）。
  • 这个 $y$ 必须在 $fl[i-1]$ 内，才能保证 $i-1$ 能继续向左传。
  • 因此 $x$ 要满足：
    1. $l_{i-1} - t_i \leq x \leq r_{i-1}$
    2. $\max(x, l_{i-1}) \in fl[i-1]$

这等价于：

• 如果 $fl[i-1]$ 与 $[l_{i-1}, r_{i-1}]$ 无交集，则不可能传到左边，$fl[i] = [-1,-1]$。
• 否则，$x$ 的范围是 $fl[i-1]$ 与 $[l_{i-1} - t_i, r_{i-1}]$ 的交集，并考虑 $x$ 对 $y$ 的约束。

---

3. 代码中的简化

你的代码实际上做了简化：

if (fl[i-1].l == -1 || fl[i-1].r == -1)
    fl[i] = fl[i-1];
else if (l[i-1] > fl[i-1].r || r[i-1] < fl[i-1].l)
    fl[i] = {-1, -1};
else if (fl[i-1].l <= l[i-1])
    fl[i].l = max(0, l[i-1] - t[i]);
else
    fl[i].l = fl[i-1].l;
fl[i].r = min(r[i-1], fl[i-1].r);

解释：

• 第一行：如果 $fl[i-1]$ 已经无效，直接继承无效状态。
• 第二行：如果窗口 $[l_{i-1}, r_{i-1}]$ 与 $fl[i-1]$ 无交集，则 $i$ 无法传到左边（因为即使传到 $i-1$，$i-1$ 也不能继续传）。
• 否则：
  • 右端点 $fl[i].r = \min(r_{i-1}, fl[i-1].r)$，因为 $x$ 不能超过 $r_{i-1}$（否则无法传），且 $y=\max(x,l_{i-1})$ 必须在 $fl[i-1]$ 内，所以 $x \leq fl[i-1].r$。
  • 左端点：
    • 如果 $fl[i-1].l \leq l_{i-1}$，意味着 $i-1$ 的最早可行时间 $\leq$ 窗口左端，那么为了传到 $i-1$，$x$ 只需满足 $x \geq l_{i-1} - t_i$（还要非负）。
    • 否则（$fl[i-1].l > l_{i-1}$），那么 $i-1$ 需要时间 $\geq fl[i-1].l$，因此 $x$ 至少为 $fl[i-1].l$（因为 $y=\max(x,l_{i-1}) \geq x$，且 $y \geq fl[i-1].l$，所以 $x \geq fl[i-1].l$）。

实际上这里隐含了 $y=\max(x,l_{i-1})$ 必须在 $fl[i-1]$ 内，所以推导出 $x$ 的范围是 $fl[i-1]$ 与 $[l_{i-1}-t_i, r_{i-1}]$ 的交集，并做了等价化简。

---

4. 双向传播

同理，我们计算 $fr[i]$：从 $i$ 能向右传到 $n$ 的到达时间范围。

初始化 $fr[n] = [0, \infty]$。

从右向左递推，逻辑对称。

---

5. 合并答案

对于服务器 $i$：

• 补丁从 $i$ 开始，要向左右两边传播。
• 初始时间 $T$ 就是补丁到达 $i$ 的时间。
• 要能传到左边，需要 $T \in fl[i]$。
• 要能传到右边，需要 $T \in fr[i]$。
• 因此 $T$ 必须在 $fl[i] \cap fr[i]$ 中。

取最小的 $T$ 就是 $\max(fl[i].l, fr[i].l)$（如果交集非空）。

如果交集为空，输出 $-1$。

---

三、算法步骤总结

1. 读入 $n, t[1..n], l[1..n-1], r[1..n-1]$。
2. 从左到右递推 $fl[i]$：
   • $fl[1] = [0, \infty]$。
   • 对 $i=2..n$，根据 $fl[i-1]$ 和边 $i-1$ 的窗口 $[l_{i-1}, r_{i-1}]$ 及 $t_i$ 计算 $fl[i]$。
3. 从右到左递推 $fr[i]$：
   • $fr[n] = [0, \infty]$。
   • 对 $i=n-1..1$，根据 $fr[i+1]$ 和边 $i$ 的窗口 $[l_i, r_i]$ 及 $t_i$ 计算 $fr[i]$。
4. 对每个 $i$：
   • 如果 $fl[i]$ 与 $fr[i]$ 无交集，输出 $-1$。
   • 否则输出 $\max(fl[i].l, fr[i].l)$。

---

四、复杂度

• 两次线性递推：$O(n)$。
• 空间 $O(n)$。

---

五、正确性要点

• 核心是独立处理左右传播，因为链式结构中，向左和向右传播是独立的，只依赖于相邻边和缓存时间。
• 递推公式正确捕捉了“到达时间必须使得下一站能继续传播”的约束。
• 最终合并时，初始时间必须同时满足左右传播条件。

---

六、举例验证

以样例 3 为例：

n=3
t = [1,2,4]
边1: [7,10]
边2: [3,5]

计算 $fl$:

• $fl[1] = [0, \infty]$
• $i=2$: $l_1=7, r_1=10$, $t_2=2$ $fl[1]$ 与 $[7,10]$ 交集 $[7,10]$，$fl[1].l=0 \leq 7$，所以 $fl[2].l = \max(0, 7-2)=5$，$fl[2].r = \min(10, \infty)=10$，得 $[5,10]$
• $i=3$: $l_2=3, r_2=5$, $t_3=4$ $fl[2]=[5,10]$ 与 $[3,5]$ 交集为 $[5,5]$，非空，$fl[2].l=5 > 3$，所以 $fl[3].l = fl[2].l = 5$，$fl[3].r = \min(5,10)=5$，得 $[5,5]$

$fr$:

• $fr[3]=[0,\infty]$
• $i=2$: $l_2=3, r_2=5$, $t_2=2$ $fr[3]$ 与 $[3,5]$ 交集 $[3,5]$，$fr[3].l=0 \leq 3$，所以 $fr[2].l = \max(0,3-2)=1$，$fr[2].r = \min(5,\infty)=5$，得 $[1,5]$
• $i=1$: $l_1=7, r_1=10$, $t_1=1$ $fr[2]=[1,5]$ 与 $[7,10]$ 无交集，所以 $fr[1]=[-1,-1]$

合并：

• $i=1$: $fl[1]=[0,\infty]$, $fr[1]=[-1,-1]$，无交集，输出 $-1$
• $i=2$: $fl[2]=[5,10]$, $fr[2]=[1,5]$，交集 $[5,5]$，输出 $5$
• $i=3$: $fl[3]=[5,5]$, $fr[3]=[0,\infty]$，交集 $[5,5]$，输出 $5$

与样例输出一致。

---

这样就完成了题解。该算法的关键在于双向独立递推传播时间可行区间，最后取交集得到最早可行初始时间。