题解：Real Mountains

题目分析

问题核心

给定一个长度为 (N) 的山高序列，通过特定编辑操作（选择谷点 (j) 并增加其高度，费用为操作前的 (h_i + h_j + h_k)），将序列转化为“山峰形态”（前半段非递减，后半段非递增），求最小总费用，结果对 (10^6 + 3) 取模。

关键约束与观察

1. 山峰形态定义：存在峰值下标 (p)，使得： [ h_1 \leq h_2 \leq \dots \leq h_p \geq h_{p+1} \geq \dots \geq h_N ] 即序列在峰值左侧非递减，右侧非递增。
2. 编辑操作规则：
   • 操作条件：存在 (i < j < k) 且 (h_i > h_j < h_k)（(j) 是谷点）。
   • 操作效果：(h_j += 1)，费用为操作前的 (h_i + h_j + h_k)。
   • 核心特点：操作仅能增加谷点高度，且费用与操作前的三个点高度相关。
3. 最小费用原则：
   • 最终序列的每个位置 (h_j) 需满足 (h_j \geq \text{lim}[j])，其中 (\text{lim}[j]) 是原始序列中 (j) 位置的“最小达标高度”（即前半段非递减的上限与后半段非递增的上限的最大值）。
   • 谷点需被增加到 (\text{lim}[j]) 才能消除“凹陷”，且每次增加的费用需按最优方式计算（批量处理同高度区间的增加操作，避免逐次计算）。

数据范围挑战

• (N \leq 10^6)，需设计 (O(N \log N)) 复杂度的算法，避免暴力模拟操作。
• 核心难点：高效识别谷点、批量计算连续高度增加的费用、利用数据结构维护区间信息。

算法设计

核心思路

1. 确定峰值与最小达标高度：
   • 选择原始序列中的一个峰值 (p)（此处选择原始序列的最大值位置，确保后续调整最小）。
   • 计算每个位置 (j) 的最小达标高度 (\text{lim}[j])：
     • 左侧（(1 \leq j \leq p)）：(\text{lim}[j] = \max(\text{lim}[j-1], h[j]))（非递减约束）。
     • 右侧（(p \leq j \leq N)）：(\text{lim}[j] = \max(\text{lim}[j+1], h[j]))（非递增约束）。
2. 离散化与区间分组：
   • 对原始高度和 (\text{lim}) 高度进行离散化，将连续的高度区间分组，便于批量处理。
3. 数据结构维护：
   • 线段树1：维护当前待处理的谷点位置（标记为“活跃”）。
   • 线段树2：维护非活跃位置的高度最小值，用于快速查询谷点左右的支撑高度（(h_i) 和 (h_k)）。
4. 批量计算费用：
   • 按离散化后的高度顺序，处理每个高度区间内的谷点，计算从当前高度增加到目标高度的总费用，累加至答案。

具体步骤

1. 确定峰值与最小达标高度

• 峰值 (p)：选择原始序列中最大值的位置（若有多个，任选其一，不影响结果）。
• 左侧非递减约束：从左到右遍历，(\text{lim}[j]) 取前一个位置的 (\text{lim}) 与当前高度的最大值。
• 右侧非递增约束：从右到左遍历，(\text{lim}[j]) 取后一个位置的 (\text{lim}) 与当前高度的最大值。

2. 离散化处理

• 收集原始高度 (h[j]) 和最小达标高度 (\text{lim}[j])，排序并去重，得到离散化后的高度数组 (b)，用于分组处理高度区间。

3. 活跃谷点标记

• 对每个位置 (j)，若 (h[j] < \text{lim}[j])，则 (j) 是需要被增加的谷点，在离散化后的高度区间中标记其“活跃”起始和结束位置（即从 (h[j]) 到 (\text{lim}[j]-1) 期间，(j) 是活跃谷点）。

4. 线段树维护与费用计算

• 初始化线段树2，存储所有位置的原始高度。
• 按离散化后的高度顺序，遍历每个高度区间 ([b[t], b[t+1]-1])：
  • 更新活跃谷点：将进入该区间的谷点标记为活跃（线段树1中设为1），离开该区间的谷点标记为非活跃（线段树1中设为0）。
  • 若当前无活跃谷点，跳过该区间。
  • 查询活跃谷点的左右边界 (l)（最左活跃谷点）和 (r)（最右活跃谷点）。
  • 查询左侧支撑高度 (pr)（(1 \sim l-1) 区间的最小高度，即谷点左侧的 (h_i)）和右侧支撑高度 (sf)（(r+1 \sim N) 区间的最小高度，即谷点右侧的 (h_k)）。
  • 批量计算该区间内每个活跃谷点增加高度的费用，累加至答案。

关键费用公式推导

对于高度区间 ([L, R])（(L = b[t], R = b[t+1]-1)），每个活跃谷点需从 (L) 增加到 (R+1)（共 (k = R - L + 1) 次操作），费用计算如下：

• 单次操作费用：对于谷点 (j)，第 (x) 次操作（(x) 从 0 到 (k-1)）的费用为 (pr + (L + x) + sf)。
• 总费用（单个谷点）：(\sum_{x=0}^{k-1} (pr + sf + L + x) = k \cdot (pr + sf + L) + \frac{k \cdot (k-1)}{2})。
• 多个活跃谷点（设共 (cnt) 个）：总费用需考虑谷点之间的相互支撑（右侧谷点的左侧支撑是左侧谷点的高度，左侧谷点的右侧支撑是右侧谷点的高度），最终推导得批量费用公式（代码中已优化合并）。

代码关键模块解析

1. 峰值与最小达标高度计算

reg int mx = 0, pos;
for (reg int i = 1; i <= n; i++)
    b[i] = a[i] = read(), cmax(mx, a[i]);
for (reg int i = 1; i <= n; i++)
    if (mx == a[i])
        pos = i; // 选择原始最大值作为峰值

// 计算左侧非递减的lim
for (reg int i = 1; i <= pos; i++)
    lim[i] = max(lim[i - 1], a[i]);
// 计算右侧非递增的lim
for (reg int i = n; i >= pos; i--)
    lim[i] = max(lim[i + 1], a[i]);

• 峰值选择原始最大值，确保后续调整的最小达标高度 (\text{lim}[j]) 最小，从而费用最低。

2. 离散化与活跃区间标记

std::sort(b + 1, b + n + 1), m = std::unique(b + 1, b + n + 1) - b - 1;
for (reg int i = 1; i <= n; i++) {
    reg int p1 = std::lower_bound(b + 1, b + m + 1, a[i]) - b; // 原始高度的离散化位置
    reg int p2 = std::lower_bound(b + 1, b + m + 1, lim[i]) - b; // 达标高度的离散化位置
    vc[p1].push_back(i); // 进入活跃区间：i 从 p1 开始活跃
    vc[p2].push_back(-i); // 离开活跃区间：i 从 p2 开始非活跃
}

• 离散化后，每个谷点的活跃区间对应离散化数组的 ([p1, p2-1]) 区间，通过向量 (vc) 标记。

3. 线段树操作

• 线段树1（sum 数组）：维护活跃谷点的位置，支持标记活跃/非活跃、查询最左/最右活跃谷点。
  • modify：更新位置的活跃状态（1 为活跃，0 为非活跃）。
  • findl/findr：查询最左/最右活跃谷点。
• 线段树2（mn 数组）：维护非活跃位置的高度最小值，支持查询区间最小值。
  • build：初始化线段树，存储原始高度。
  • update：更新位置的高度（活跃谷点设为无穷大，避免被查询到）。
  • query：查询区间最小高度（即支撑高度 (pr) 或 (sf)）。

4. 批量费用计算

reg int l = findl(1, 1, n), r = findr(1, 1, n);
reg int pr = query(1, 1, n, 1, l - 1), sf = query(1, 1, n, r + 1, n);
// 计算批量费用
ans = (ans + 1ll * (b[t] + b[t + 1] - 1) * (b[t + 1] - b[t]) / 2 % mod * sum[1]) % mod;
ans = (ans + 1ll * (b[t + 1] - b[t]) * (pr + sf)) % mod;
if (sum[1] > 1) {
    ans = (ans + 1ll * (b[t + 1] - b[t]) * (b[t] + 1 + b[t + 1]) / 2 % mod * (2 * (sum[1] - 2) + 1)) % mod;
    ans = (ans + 1ll * b[t + 1] * (b[t + 1] - b[t])) % mod;
}

• 费用公式整合了单个谷点的多次操作费用和多个谷点的相互支撑费用，通过批量计算避免逐次操作模拟，确保 (O(N \log N)) 复杂度。

时间复杂度与空间复杂度

• 时间复杂度：(O(N \log N))。离散化 (O(N \log N))，线段树操作（更新、查询）均为 (O(\log N))，每个位置最多被更新两次，总时间线性对数。
• 空间复杂度：(O(N))。存储原始序列、离散化数组、线段树节点、活跃区间标记向量，均为线性空间。

关键结论

1. 最小达标高度的必要性：每个位置的最终高度必须至少为 (\text{lim}[j])，否则无法满足山峰形态，这是后续费用计算的基础。
2. 批量处理的高效性：将连续高度的增加操作批量计算，避免逐次模拟，大幅降低时间复杂度，适配 (N \leq 10^6) 的数据规模。
3. 数据结构的核心作用：线段树用于维护活跃谷点和支撑高度，确保快速查询和更新，是算法高效运行的关键。