题意理解

我们有 $N$ 个天线，第 $i$ 个天线高度为 $H_i$，它只能向距离在 $[A_i, B_i]$ 内的天线发送信息。 如果天线 $i$ 和 $j$ 可以互相通信（即 $|i-j| \in [A_i,B_i]$ 且 $|i-j| \in [A_j,B_j]$），则它们的通信成本为 $|H_i - H_j|$。

给定 $Q$ 个询问 $[L_j, R_j]$，问区间内所有天线对中，能互相通信的最大成本是多少，若没有则输出 $-1$。

---

第一步：直接暴力思路

最直接的方法是枚举所有 $i < j$，检查它们是否能互相通信，然后计算 $|H_i - H_j|$，取最大值。 检查条件为：

$|i-j| \ge A_i$ 且 $|i-j| \le B_i$

$|i-j| \ge A_j$ 且 $|i-j| \le B_j$

即：

$$A_i \le j-i \le B_i 且 A_j \le j-i \le b_j$$

对于询问 $[L,R]$，只考虑 $i,j \in [L,R]$。

复杂度：$O(N^2)$ 对每对天线，再乘 $Q$ 会超时。

第二步：固定一个天线，考虑它能和谁通信

对于天线 $i$，它能发送信息的天线 $j$ 必须满足：

$$i+A_i≤j≤i+B_i ​$$

并且 $j$ 能接收 $i$ 的信号需要满足：

$$j−B_j≤i≤j−A_j ​$$

所以 $(i,j)$ 能互相通信的条件是：

$$\begin{cases} i + A_i \le j \le i + B_i \\ j - B_j \le i \le j - A_j \end{cases} $$

第三步：转化为二维数点问题

我们可以把问题看作：每个天线 $i$ 对应一个“事件”，询问区间 $[L,R]$ 内所有满足互相通信条件的天线对 $(i,j)$ 的最大 $|H_i - H_j|$。

这类区间最值问题常用扫描线 + 线段树/树状数组解决。

---

关键观察

对于一对 $(i,j)$，$|H_i - H_j| = \max(H_i - H_j, H_j - H_i)$。 因此我们可以分别考虑两种情况：

$H_i \ge H_j$，则成本 $= H_i - H_j$

$H_j \ge H_i$，则成本 $= H_j - H_i$

所以问题变成：对于所有合法 $(i,j)$，求 $\max(H_i - H_j, H_j - H_i)$。

第四步：离线处理 我们可以对询问按右端点排序，从左到右扫描 $j$，维护之前所有 $i$ 的信息。

对于固定的 $j$，哪些 $i$ 能与之互相通信？

条件：

$$\big( i \in [j - B_j, j - A_j] \big) \ \land\ \big( j \in [i + A_i, i + B_i] \big) $$

第一个条件给出了 $i$ 的范围，第二个条件是对 $i$ 的限制，可以看作 $i$ 在插入时带有生效区间 $[i+A_i, i+B_i]$。

第五步：扫描线 + 线段树维护 我们按 $j$ 从小到大扫描：

当 $j$ 进入 $i$ 的生效区间 $[i+A_i, i+B_i]$ 时，将 $i$ 加入数据结构。

当 $j$ 离开 $i$ 的生效区间（$j > i+B_i$）时，将 $i$ 移除。

对于每个 $j$，我们查询区间 $[j-B_j, j-A_j]$ 内的所有 $i$，计算 $H_j - H_i$（当 $H_j \ge H_i$）或 $H_i - H_j$（当 $H_i \ge H_j$）的最大值。

---

具体实现方法

我们需要维护两种信息：

对于 $H_j \ge H_i$，求 $H_j - H_i$ 最大 → 即求区间内 $H_i$ 的最小值。

对于 $H_i \ge H_j$，求 $H_i - H_j$ 最大 → 即求区间内 $H_i$ 的最大值。

因此我们可以用两棵线段树：

一棵维护区间 $H_i$ 最大值

一棵维护区间 $H_i$ 最小值

当扫描到 $j$ 时：

在 $[j-B_j, j-A_j]$ 区间内，用 $H_j - \min H_i$ 更新答案（如果 $\min$ 存在且 $H_j \ge \min$）

用 $\max H_i - H_j$ 更新答案（如果 $\max$ 存在且 $\max \ge H_j$）

第六步：处理互相通信条件 注意：我们上面只考虑了 $j$ 对 $i$ 的范围限制 $[j-B_j, j-A_j]$，而 $i$ 对 $j$ 的限制 $[i+A_i, i+B_i]$ 是通过扫描线加入/移除 $i$ 来保证的。

这样我们确实覆盖了互相通信的两个条件。

第七步：算法流程

离线所有询问，按 $R$ 排序。

准备两个线段树：seg_max 和 seg_min，初始值设为 $-\infty$ 和 $+\infty$。

准备事件：

对于每个 $i$，在 $j = i+A_i$ 时将 $i$ 插入数据结构

在 $j = i+B_i+1$ 时将 $i$ 移除

按 $j=1 \dots N$ 扫描：

处理所有在 $j$ 时刻加入的 $i$，更新线段树位置 $i$ 为 $H_i$

处理所有在 $j$ 时刻移除的 $i$，更新线段树位置 $i$ 为无效值

对于所有 $R_j = j$ 的询问 $[L, j]$：

在区间 $max(L, j-B_j), j-A_j$ 内（如果区间有效）查询 minH 和 maxH

用 $H_j - minH$ 和 $maxH - H_j$ 更新该询问的答案

输出每个询问的最终答案（若未更新则输出 $-1$）

第八步：复杂度

每个 $i$ 加入/移除一次：$O(N)$ 次操作

每个询问查询一次：$O(Q)$ 次操作

线段树操作 $O(\log N)$

总复杂度 $O((N+Q)\log N)$，可过。

---

公式总结

互相通信条件：

$$max(A_i,A_j) \le j-i \le min(B_i,B_j)$$

成本：

$$cost(i,j)=|H_i-H_j|=max(H_i-H_j,H_j-H_i)$$

扫描线维护：

加入事件：$j = i + A_i$ 时加入 $i$

移除事件：$j = i + B_i + 1$ 时移除 $i$

查询区间：$i \in [j - B_j, j - A_j]$

这样我们就得到了一个高效的 $O((N+Q)\log N)$ 解法。