题目翻译

有 $N$ 座山峰，第 $i$ 座高度为 $h_i$。
若在第 $i$ 座山峰建一个高度为 $p$ 的灯塔，它能照亮第 $j$ 座山峰当且仅当：

$$h_j \le h_i + p - \sqrt{|i-j|}$$

要求对每座山峰 $i$，求能照亮所有其他山峰的最小灯塔高度 $p_i$。

---

问题转化

由条件：

$$h_j \le h_i + p_i - \sqrt{|i-j|}$$

可得：

$$p_i \ge h_j + \sqrt{|i-j|} - h_i$$

因此：

$$p_i = \max_{1 \le j \le N} \left( h_j + \sqrt{|i-j|} \right) - h_i $$

---

直接暴力的问题

直接对每个 $i$ 枚举 $j$ 是 $O(N^2)$ 的，$N \le 10^5$ 会超时。

---

优化思路

定义：

$$f(i) = \max_{j=1}^N \left( h_j + \sqrt{|i-j|} \right) $$

那么 $p_i = \lceil f(i) - h_i \rceil$（因为 $p_i$ 是非负整数，样例是向上取整）。

---

决策单调性

考虑函数 $w(j,i) = h_j + \sqrt{|i-j|}$。
对于固定的 $j$，$w(j,i)$ 随 $|i-j|$ 增大而缓慢增加（$\sqrt{x}$ 增长越来越慢）。
这种形式的函数具有决策单调性：
即，如果定义 $opt(i)$ 是使 $w(j,i)$ 最大的 $j$，那么 $opt(i)$ 随着 $i$ 增大而单调不减。

---

分治解法

我们可以用 分治优化 DP 的方法计算 $f(i)$：

1. 先考虑 $j \le i$ 的部分：
   $g_1(i) = \max_{j \le i} \left( h_j + \sqrt{i-j} \right)$
2. 再考虑 $j \ge i$ 的部分：
   $g_2(i) = \max_{j \ge i} \left( h_j + \sqrt{j-i} \right)$
3. 最后 $f(i) = \max(g_1(i), g_2(i))$

这两部分是对称的，可以用同样的分治方法解决。

---

分治过程

对于 $g_1$：

• 定义 solve(l, r, L, R) 表示计算区间 $[l, r]$ 的 $g_1$，已知最优决策点在 $[L, R]$。
• 取 $mid = (l+r)/2$，在 $[L, \min(R, mid)]$ 中找到最优决策点 $k$。
• 递归 solve(l, mid-1, L, k) 和 solve(mid+1, r, k, R)。

同理处理 $g_2$（方向相反）。

---

复杂度

每层分治扫描的总长度是 $O(N)$，共 $O(\log N)$ 层，所以总复杂度 $O(N \log N)$。

---