题目大意

给定长度为 $n$ 的序列 $h_1, h_2, \dots, h_n$，对于每个位置 $i$ 有两个可能的取值：

• $h_i$（石柱本身）
• $h'_i = 2L - h_i$（石柱的像）

求有多少区间 $[u, v]$（$1 \le u < v \le n$）满足：存在正实数 $L$，使得可以给每个位置选择 $h_i$ 或 $h'_i$，构成严格递增序列。

关键观察

1. 约束条件分析

对于相邻位置 $i$ 和 $i+1$，有四种选择组合：

1. $(h_i, h_{i+1})$：要求 $h_i < h_{i+1}$
2. $(h_i, h'_{i+1})$：要求 $h_i < 2L - h_{i+1}$，即 $L > \frac{h_i + h_{i+1}}{2}$
3. $(h'_i, h_{i+1})$：要求 $2L - h_i < h_{i+1}$，即 $L < \frac{h_i + h_{i+1}}{2}$
4. $(h'_i, h'_{i+1})$：要求 $2L - h_i < 2L - h_{i+1}$，即 $h_i > h_{i+1}$

2. 可行性条件

对于区间 $[u, v]$，我们需要检查是否存在 $L > 0$ 满足所有相邻位置的约束。

设 $L$ 的可行范围为 $[L_{\min}, L_{\max}]$，初始为 $(0, +\infty)$。

对于每个相邻位置：

• 情况1：无条件（如果 $h_i < h_{i+1}$）
• 情况2：$L_{\min} = \max(L_{\min}, \frac{h_i + h_{i+1}}{2})$
• 情况3：$L_{\max} = \min(L_{\max}, \frac{h_i + h_{i+1}}{2})$
• 情况4：无条件（如果 $h_i > h_{i+1}$）

如果最终 $L_{\min} < L_{\max}$，则区间可行。

算法设计

双指针法

核心思想：对于每个起点 $u$，找到最大的 $v$ 使得 $[u, v]$ 可行，那么所有 $[u, u+1], [u, u+2], \dots, [u, v]$ 都可行。

算法步骤：

1. 初始化指针 $r = 1$
2. 对于每个 $l = 1 \dots n$：
   • 如果 $r < l$，则 $r = l$
   • 不断尝试扩展 $r$，直到 $[l, r+1]$ 不可行
   • 答案加上 $r - l$（即区间 $[l, l+1], \dots, [l, r]$ 都可行）
3. 输出总答案

时间复杂度：$O(n)$，因为每个位置最多被左右指针各访问一次。

实现细节

1. 约束维护

我们需要维护当前区间 $[l, r]$ 的 $L$ 范围 $[L_{\min}, L_{\max}]$。

当从 $[l, r]$ 扩展到 $[l, r+1]$ 时，只需检查新增的相邻对 $(r, r+1)$ 的约束。

当左指针 $l$ 右移时，需要删除 $(l, l+1)$ 的约束影响。但直接删除比较困难，可以采用另一种方法：

2. 可行的实现方法

对于每个起点 $l$，重新计算从 $l$ 开始的约束，利用之前的信息：

• 如果 $[l, r]$ 可行，那么 $[l+1, r]$ 很可能也可行
• 实际上，我们可以从 $r$ 开始继续扩展，而不是从 $l+1$ 重新开始

具体实现时，维护当前 $L_{\min}$ 和 $L_{\max}$，当加入新位置时更新约束，如果 $L_{\min} \ge L_{\max}$ 则停止扩展。

复杂度分析

• 时间复杂度：$O(n)$，每个位置最多被右指针访问一次
• 空间复杂度：$O(n)$，存储高度数组

总结

本题的关键在于：

1. 将问题转化为关于 $L$ 的不等式组
2. 发现区间可行性的单调性质
3. 使用双指针高效统计所有合法区间

通过维护 $L$ 的可行范围，我们可以在 $O(n)$ 时间内解决该问题。