注意事项

由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "raft.h"。

题目描述

题目译自 2025년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T4 「뗏목 제작」

在郁郁葱葱的 $KOI$ 森林和 $IOI$ 森林中，树木繁茂。$KOI$ 森林有 $N$ 棵树，从左到右依次编号为 $0$ 到 $N-1$；$IOI$ 森林有 $M$ 棵树，同样从左到右编号为 $0$ 到 $M-1$。$KOI$ 森林中第 $i$ $(0 \leq i \leq N-1)$ 棵树的高度是 $A[i]$，$IOI$ 森林中第 $j$ $(0 \leq j \leq M-1)$ 棵树的高度是 $B[j]$。

你的部落居住在一个孤岛上，有向海神祈祷的古老传统。为了举行仪式，你需要打造一艘木筏，材料将从这两片森林中砍伐而来。

乘木筏前往岛屿十分危险，因此你希望木筏尽可能稳固。木筏由树木横向拼接而成，包含的矩形面积越大越稳定。具体来说，假设木筏由左至右的树高依次为 $H[0], H[1], \ldots, H[L-1]$，其稳定性定义为：

$$\max_{0 \leq s \leq l \leq L-1} \left( \min(H[s], \ldots, H[l]) \times (l - s + 1) \right) $$

这意味着，对于所有可能的连续区间 $[s, l]$，取该区间内树高的最小值，乘以区间宽度 $(l - s + 1)$，然后求所有结果的最大值。

根据部落传统，木筏的树木必须遵循以下规则：

• 砍伐的所有树都要用于木筏。
• 从 $KOI$ 森林砍来的树必须保持原有顺序，即如果树 $X$ 在森林中位于树 $Y$ 左侧，那么在木筏上 $X$ 也必须在 $Y$ 左侧。
• 从 $IOI$ 森林砍来的树同样需保持原有顺序。

你决定砍伐 $KOI$ 森林中从 $0$ 到 $N-1$ 的全部 $N$ 棵树，但 $IOI$ 森林中具体砍哪些树尚未确定。你需要回答 $Q$ 个编号从 $0$ 到 $Q-1$ 的问题，这些问题由长度为 $Q$ 的数组 $L$ 和 $R$ 表示。第 $k$ $(0 \leq k \leq Q-1)$ 个问题是：若从 $IOI$ 森林砍伐编号在 $L[k]$ 到 $R[k]$ 之间的树，木筏的最大稳定性是多少？

---

实现细节

你需要实现以下函数：

std::vector<long long> max_stability(std::vector<int> A, std::vector<int> B,
                                     std::vector<int> L, std::vector<int> R)

• $A$：长度为 $N$ 的整数数组，表示 $KOI$ 森林树高。
• $B$：长度为 $M$ 的整数数组，表示 $IOI$ 森林树高。
• $L$, $R$：长度为 $Q$ 的整数数组，表示每次询问的范围。
• 函数需返回一个长度为 $Q$ 的整数数组 $C$，其中对于 $0 \leq k \leq Q-1$，$C[k]$ 表示用 $KOI$ 森林所有树及 $IOI$ 森林编号从 $L[k]$ 到 $R[k]$ 的树制作木筏时，可能的最大稳定性。
• 每个测试用例中，该函数只被调用一次。
• 你提交的代码不得包含任何输入输出函数。

---

样例 1

假设 $N=5$，$M=4$，$Q=2$，$A=[3,3,1,6,1]$，$B=[3,5,7,6]$，$L=[0,0]$，$R=[1,3]$。

评测程序调用：

max_stability([3, 3, 1, 6, 1], [3, 5, 7, 6], [0, 0], [1, 3])

• 当 $L[0]=0$, $R[0]=1$ 时，最大稳定性为 $12$。例如：
  • 木筏从左到右依次为 $KOI$ 的 $0$、$1$ 号树，$IOI$ 的 $0$、$1$ 号树，$KOI$ 的 $2$、$3$、$4$ 号树，高度为 $H=[3,3,3,5,1,6,1]$。
  • 取 $[0, 3]$，最小高度 $\min(H[0], H[1], H[2], H[3]) = 3$，宽度 $4$，稳定性 $3 \times 4 = 12$。
• 当 $L[1]=0$, $R[1]=3$ 时，最大稳定性为 $20$。例如：
  • 木筏从左到右依次为 $KOI$ 的 $0$、$1$、$2$ 号树，$IOI$ 的 $0$、$1$、$2$、$3$ 号树，$KOI$ 的 $3$、$4$ 号树，高度为 $H=[3,3,1,3,5,7,6,6,1]$。
  • 取 $[4, 7]$，最小高度 $\min(H[4], H[5], H[6], H[7]) = 5$，宽度 $4$，稳定性 $5 \times 4 = 20$。

函数应返回 $[12, 20]$。

---

样例 2

评测程序调用：

max_stability([9, 9, 9, 9, 9], [1, 2, 3, 4, 5, 6, 7, 8], [0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7])

函数应返回 $[45, 45, 45, 45, 45, 45, 45, 49]$。

---

样例 3

评测程序调用：

max_stability([1000000000, 1000000000, 1000000000], [1000000000, 1000000000], [0], [1])

函数应返回 $[5000000000]$。

---

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N, M \leq 150000$
• $1 \leq Q \leq 500000$
• 对于所有 $0 \leq i \leq N-1$，$1 \leq A[i] \leq 10^{9}$
• 对于所有 $0 \leq j \leq M-1$，$1 \leq B[j] \leq 10^{9}$
• 对于所有 $0 \leq k \leq Q-1$，$0 \leq L[k] \leq R[k] \leq M-1$

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
1	10	$N, M, Q \leq 3000$
2	8	$Q \leq 300$
3	20	对于所有 $0 \leq k \leq Q-1$，$L[k] = 0$ 或 $B[L[k]-1] < \min(B[L[k]], B[L[k]+1], \ldots, B[R[k]])$； 对于所有 $0 \leq k \leq Q-1$，$R[k] = M-1$ 或 $B[R[k]+1] < \min(B[L[k]], B[L[k]+1], \ldots, B[R[k]])$
4	6	对于所有 $0 \leq i \leq N-1$，$A[i] \leq 50$；对于所有 $0 \leq j \leq M-1$，$B[j] \leq 50$
5	14	对于所有 $0 \leq i \leq N-1$，$A[i]$ 恒定不变
6	11	对于所有 $0 \leq j \leq M-2$，$B[j] \geq B[j+1]$
7	13	对于所有 $0 \leq k \leq Q-1$，$L[k] = 0$
8	7	对于所有 $0 \leq k \leq Q-1$，$R[k] - L[k]$ 相同
9	11	无附加限制

---

示例评测程序

示例评测程序接收以下格式的输入：

第 1 行：N M Q
第 2 行：A[0] A[1] … A[N-1]
第 3 行：B[0] B[1] … B[M-1]
第 4+k (0 ≤ k ≤ Q-1) 行：L[k] R[k]

输出格式如下：

第 1+k (0 ≤ k ≤ Q-1) 行：设 max_stability 返回值为 C，则输出 C[k]

请注意，示例评测程序可能与实际评测程序有所不同。