题解：B. Speedbreaker

提示 1

什么时候答案为 $0$？

提示 2

从城市 $x$ 开始等价于将 $a_x$ 设为 $1$。

---

详细题解

1. 基本思路与必要区间

在时刻 $t$，考虑所有满足 $a_i \le t$ 的城市。这些城市构成一个最小包含区间 $[l_t, r_t]$，即最小的区间使得所有 $a_i \le t$ 的城市都落在其中。

关键观察：
在时刻 $t$，你必须已经征服了 $[l_t, r_t]$ 中的所有城市。
因为如果 $[l_t, r_t]$ 中还有城市未被征服，那么它的截止时间 $\le t$ 就会被违反。

因此，$[l_t, r_t]$ 的长度必须 $\le t$。
若存在某个 $t$ 使得 $r_t - l_t + 1 > t$，则无法获胜，答案为 $0$。

---

2. 构造获胜策略

如果对所有 $t$ 都有 $r_t - l_t + 1 \le t$，那么至少存在一种获胜策略。
一种构造方法是：

依次访问 “时刻 $1$ 的最小区间”，然后 “时刻 $2$ 的最小区间”，……，直到 “时刻 $n$ 的最小区间”。

注意：当访问 “时刻 $t$ 的最小区间” 时，当前时间恰好等于该区间的长度（因为你每次只能扩展相邻城市），而该长度 $\le t$。
这样，在时刻 $t$ 结束时，你已经征服了 $[l_t, r_t]$ 中的所有城市（可能还多了一些），满足要求。

---

3. 起始城市的影响

选择起始城市 $x$ 等价于将 $a_x$ 设为 $1$（因为你在时刻 $1$ 征服 $x$）。
这会影响最小区间的计算。

假设原数组的最小区间为 $[l, r]$。
将 $a_x$ 改为 $1$ 后，新区间可能变为：

• 若 $x < l$：新区间为 $[x, r]$
• 若 $x > r$：新区间为 $[l, x]$
• 若 $l \le x \le r$：新区间不变，仍为 $[l, r]$

要求：对于每个 $t$，新区间的长度必须 $\le t$。

---

4. 转化为对 $x$ 的限制

以 $x < l$ 为例，新区间 $[x, r]$ 的长度为 $r - x + 1$，要求 $r - x + 1 \le t$。
即 $x \ge r - t + 1$。

同理，若 $x > r$，要求 $x \le l + t - 1$。

若 $l \le x \le r$，则原区间长度 $r - l + 1$ 必须已经 $\le t$（否则原数组本身就不满足，答案为 $0$）。

因此，对于每个 $t$，允许的 $x$ 范围是：

$$x \in [\max(l_t, \, r_t - t + 1), \; \min(r_t, \, l_t + t - 1)] $$

更简洁地，可以写成：

$$x \in [l_t, r_t] \cap [r_t - t + 1, \; l_t + t - 1] $$

实际上，这等价于要求 $x$ 同时满足：

• $x \ge r_t - t + 1$
• $x \le l_t + t - 1$

并且 $x$ 还要落在 $[1, n]$ 范围内。

---

5. 最终区间

对所有 $t = 1, 2, \dots, n$ 取上述区间的交集，得到起始城市 $x$ 的允许范围。

最终答案为这个交集的长度（若交集非空）。

---

6. 另一种等价形式

该题与 2018F3 - Speedbreaker Counting (Hard Version) 的结论一致：
允许的起始城市 $x$ 必须满足：

[ x \in \bigcap_{i=1}^n [i - a_i + 1, ; i + a_i - 1] ]

这个区间的长度即为答案。

证明思路：
从城市 $i$ 必须在时刻 $\le a_i$ 被征服，意味着在征服过程中，从起点到 $i$ 的距离（步数）$\le a_i - 1$。
这等价于起点 $x$ 与 $i$ 的距离 $\le a_i - 1$，即 $|x - i| \le a_i - 1$，也就是 $x \in [i - a_i + 1, i + a_i - 1]$。

对所有 $i$ 取交集即可。

---

7. 算法实现

• 初始化 $L = 1$，$R = n$
• 遍历 $i = 1$ 到 $n$：
  • $L = \max(L, i - a_i + 1)$
  • $R = \min(R, i + a_i - 1)$
• 若 $L > R$，答案为 $0$；否则答案为 $R - L + 1$

时间复杂度：$O(n)$，总复杂度 $O(\sum n)$。

---

总结

• 关键概念：最小包含区间 $[l_t, r_t]$ 必须在时刻 $t$ 内被完全征服。
• 选择起始城市相当于修改 $a_x = 1$，从而影响所有最小区间。
• 最终允许的起始城市范围是所有 $[i - a_i + 1, i + a_i - 1]$ 的交集。