问题分析

我们有 $n$ 个块，每个块宽 $1$，高 $a_i$，长 $b_i$。
我们要找一个长方体，底面是连续的若干个块（宽度 $w$），高度不能超过这些块的最小 $a_i$，长度不能超过这些块的最小 $b_i$。

体积公式为：

$$V = w \times \min(a_{l..r}) \times \min(b_{l..r})$$

其中 $w = r-l+1$。

---

思路

1. 二维直方图最大矩形类比

在二维直方图最大矩形问题中，我们通常用单调栈来枚举每个高度作为最小值的区间，然后计算面积。

这里变成了两个维度 $(a_i, b_i)$ 同时限制，不能直接分开处理。

---

2. 分治思路

一个经典做法是使用分治：

• 在区间 $[L, R]$ 中，取中点 $M = \lfloor (L+R)/2 \rfloor$。
• 最大长方体要么完全在左半 $[L, M]$，要么完全在右半 $[M+1, R]$，要么跨越中点。
• 递归解决左右两半。
• 重点处理跨越中点的情况。

---

3. 跨越中点的处理

假设我们固定一个区间 $[l, r]$ 跨越 $M$，那么：

$$\min a = \min(\min(a_{l..M}), \min(a_{M+1..r}))$$ $$\min b = \min(\min(b_{l..M}), \min(b_{M+1..r}))$$

我们可以从中点向左右扩展，记录扩展过程中 $a$ 和 $b$ 的最小值。

---

具体方法

1. 从中点 $M$ 向左扩展 $i = M$ 到 $L$，记录：

   • $minA_L[k] = \min(a_{k..M})$
   • $minB_L[k] = \min(b_{k..M})$ 其中 $k$ 从 $M$ 到 $L$。

2. 从中点 $M+1$ 向右扩展 $j = M+1$ 到 $R$，记录：

   • $minA_R[j] = \min(a_{M+1..j})$
   • $minB_R[j] = \min(b_{M+1..j})$

3. 枚举左端点 $l$ 从 $M$ 到 $L$，对于每个 $l$，我们希望在右半部分找到 $r$ 使得：

   $$(M-l+1 + r-M) \times \min(minA_L[l], minA_R[r]) \times \min(minB_L[l], minB_R[r]) $$

   最大。

---

4. 优化枚举

直接枚举 $l, r$ 是 $O(n^2)$ 的，不可行。

注意：当 $l$ 固定时，随着 $r$ 增加，$minA_R[r]$ 可能减小或不变，$minB_R[r]$ 也可能减小或不变。

我们可以把右半部分按照 $minA_R[r]$ 的变化分成若干段（单调栈思想），每段内 $minA_R[r]$ 相同，并且 $minB_R[r]$ 是单调的（因为 $minB_R[r]$ 也是单调递减的）。

这样，对于每个 $l$，我们只需要在右半部分的这些段中找最优解。

---

5. 双指针/凸壳思想

实际上，这是一个二维优化问题：

$$\text{最大化 } (lenL + lenR) \times \min(A_l, A_r) \times \min(B_l, B_r) $$

其中 $lenL = M-l+1$, $lenR = r-M$。

我们可以将右半部分按 $A_r$ 排序（从大到小），然后维护一个类似凸壳的结构，因为当 $A_r \ge A_l$ 时，体积为：

$$(lenL + lenR) \times A_l \times \min(B_l, B_r)$$

当 $A_r < A_l$ 时，体积为：

$$(lenL + lenR) \times A_r \times \min(B_l, B_r)$$

两种情况都可以用双指针或单调栈优化。

---

6. 实现细节

• 分治递归深度 $O(\log n)$。
• 每一层处理 $O(n)$ 或 $O(n \log n)$。
• 最终复杂度 $O(n \log^2 n)$ 或 $O(n \log n)$，取决于实现。