问题分析

我们有 $N$ 个高度互不相同的信号塔排成一行。对于给定的干扰参数 $\delta$，两个塔 $i$ 和 $j$ ($i < j$) 能够通信的条件是：存在中间塔 $k$ ($i < k < j$) 使得：

$$H[i] \leq H[k] - \delta \quad \text{且} \quad H[j] \leq H[k] - \delta $$

我们需要回答 $Q$ 个查询：在区间 $[L, R]$ 内，最多能选择多少个塔，使得它们两两之间都能通信。

关键观察

$1$. 通信条件的转化：塔 $i$ 和 $j$ 能通过塔 $k$ 通信 ⇔ $H[k] \geq \max(H[i], H[j]) + \delta$

$2$. 中间塔的作用：较高的塔更有可能作为通信的中间节点

$3$. 独立集结构：最优解中的塔形成一个特殊结构，其中较高的塔服务于较低的塔

解法思路

核心数据结构

代码使用了三种主要数据结构：

$1$. ST表：用于 $O(1)$ 查询区间最大值 2. 笛卡尔树：表示塔的高度关系，每个节点是其子树中的最大值
3. 可持久化线段树：维护每个塔作为中间塔的能力

算法步骤

预处理阶段 (init)：

$1$. 构建ST表：预处理区间最大值，支持快速查询

for (int j = 1; j <= 19; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
        mn[j][i] = min(mn[j - 1][i], mn[j - 1][i + (1 << (j - 1))]);
        mx[j][i] = max(mx[j - 1][i], mx[j - 1][i + (1 << (j - 1))]);
    }
}

$2$. 构建笛卡尔树：计算每个塔的左右边界

• L[i]：左边第一个比 $H[i]$ 小的位置
• R[i]：右边第一个比 $H[i]$ 小的位置
• 同时预处理倍增数组用于快速跳转

$3$. 计算限制值：对于每个塔 $i$，计算其作为中间塔能服务的最大 $\delta$

lim[i] = min(左边区间最大值 - h[i], 右边区间最大值 - h[i])

$4$. 构建可持久化线段树：将 lim[i] 离散化后插入，支持区间查询

查询阶段 (max_towers)：

$1$. 基础统计：查询区间内满足 lim[i] >= d 的塔数量

ans += st.qry(tr[r], tr[l-1], 1, Dc, disc(d), Dc);

$2$. 边界处理：使用倍增检查区间边界的特殊塔

• 找到满足条件的左右边界塔
• 检查它们是否能被包含在答案中

复杂度分析

• 预处理：$O(N \log N)$

  • ST表：$O(N \log N)$
  • 笛卡尔树：$O(N)$
  • 可持久化线段树：$O(N \log N)$

• 单次查询：$O(\log N)$

  • 线段树查询：$O(\log N)$
  • 倍增操作：$O(\log N)$

正确性证明

该解法的正确性基于以下关键点：

$1$. 完备性：所有能作为中间塔服务其他塔的塔都被考虑在内 2. 独立性：选择的塔之间通过中间塔形成连通结构 3. 最优性：贪心地选择能服务最多其他塔的高塔

代码实现细节

// 关键函数：计算限制值
for (int i = 1; i <= n; i++) {
    int llim = L[i] ? ((L[i] + 1 < i) ? gmx(L[i] + 1, i - 1).first - h[i] : 0) : (int)1E9;
    int rlim = R[i] ? ((R[i] - 1 > i) ? gmx(i + 1, R[i] - 1).first - h[i] : 0) : (int)1E9;
    lim[i] = min(llim, rlim);
}

这段代码计算每个塔 $i$ 作为中间塔时，左右两侧需要满足的高度条件的最小值。

总结

本题的解法展示了如何将复杂的通信条件转化为基于高度的比较问题，并利用笛卡尔树和可持久化数据结构实现高效查询。关键在于发现通信关系的单调性，从而设计出 $O(\log N)$ 的查询算法。

算法标签：笛卡尔树、可持久化线段树、区间查询、倍增法、ST表