题意简化

$n$ 座塔，第 $i$ 座高 $H_i$，由砖块组成。
每次最多带 $k$ 块砖，规则：

1. 从任意塔底开始
2. 可向上/左右同高度移动（该位置需有砖块）
3. 可放置砖块（可悬空），放置后必须移动到该位置

求最少运送次数。

$n \le 10^5$，$H_i, k \le 10^9$。

核心思路：分治 + 贪心

1. 问题转化

将搭建过程看作二维平面上放砖块：

• $x$ 轴：塔的编号 $1..n$
• $y$ 轴：高度 $1..H_i$

规则等价于：

• 只能站在已有砖块或刚放的砖块上
• 可向上/左右（同高度）移动
• 每次最多带 $k$ 块砖

2. 关键观察

分治思想：找到最矮的塔 $mid$，高度 $h = H_{mid}$。

将区域分为三部分：

1. 左半区 $[l, mid-1]$
2. 最矮点 $mid$
3. 右半区 $[mid+1, r]$

搭建策略：

• 先搭建左右半区到高度 $h$（递归）
• 然后在整个区间 $[l, r]$ 搭建高度 $h$ 到实际高度

3. 数据结构

• ST表：快速查询区间最小值位置 $mid$
• Data结构：记录两个信息
  • ans：最少运送次数
  • r：当前剩余的砖块（可为负，表示还需要多少砖）

4. 分治算法

Data solve(l, r, h)：搭建区间 $[l, r]$ 从当前高度 $h$ 到实际高度。

步骤：

1. 找到最矮位置 $mid$，高度 $H_{mid}$
2. 递归处理左右子区间到高度 $H_{mid}$
3. 合并结果：左右次数相加，剩余砖块累加
4. 计算搭建整个区间从 $h$ 到 $H_{mid}$ 的砖块需求

砖块计算：

• 需要搭建的砖块数 = $(r-l+1) \times (H_{mid} - h)$
• 这些砖块可以一次运送（最多 $k$ 块）

5. Data结构操作

add(val)：处理一批砖块的运送

• r += val：更新剩余砖块
• 如果 $r > 0$（有多余砖块）：
  • 计算还需要运送次数：$\lceil \frac{r}{k} \rceil$
  • 更新 ans
  • 减去已运送的砖块：$r \leftarrow r - \lceil \frac{r}{k} \rceil \times k$
• 注意：$r$ 可为负数，表示还需要砖块

算法步骤

1. 预处理：

   • 建立ST表，$O(n \log n)$
   • 支持 $O(1)$ 查询区间最小值位置

2. 递归分治：

   • 找到最矮位置
   • 递归处理左右
   • 合并计算

3. 合并策略：

   • 左右子问题的答案相加
   • 剩余砖块累加
   • 计算当前层需要的砖块

复杂度分析

• ST表预处理：$O(n \log n)$
• 分治递归：$O(n \log n)$（类似建笛卡尔树）
• 总复杂度：$O(n \log n)$

关键点

1. 为什么分治正确？

最矮点将问题分解，左右可独立搭建到该高度，然后整体向上搭建。

2. 贪心运送策略

• 有多余砖块就尽量多用
• 每次尽量带满 $k$ 块
• 剩余砖块可跨层使用

3. 负数剩余砖块

r 可为负，表示还需要砖块，这些砖块会在后续运送中补齐。

样例解释

输入：

5 10
2 1 2 1 2

塔高：2 1 2 1 2

过程：

1. 最矮位置：2和4（高度1）
2. 递归搭建左右到高度1
3. 整体搭建到高度2

计算：

• 总砖块数：2+1+2+1+2 = 8
• 每次最多10块
• 最少需要 $\lceil 8/10 \rceil = 1$ 次？不对

实际：

• 左右递归需要运送
• 合并后需要3次

输出：3

代码特点

• ST表快速查询最矮位置
• 分治递归结构
• Data结构封装运送逻辑
• 注意整数溢出用 long long