注意事项

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

• 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} (\min(H[s], \ldots, H[l]) \times (l - s + 1)) $$

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

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

1. 砍伐的所有树都要用于木筏。
2. 从 KOI 森林砍来的树必须保持原有顺序，即如果树 $X$ 在森林中位于树 $Y$ 左侧，那么在木筏上 $X$ 也必须在 $Y$ 左侧。
3. 从 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]\ \ldots\ A[N-1]$
• 第 $3$ 行：$B[0]\ B[1]\ \ldots\ B[M-1]$
• 第 $4+k$ $(0 \leq k \leq Q-1)$ 行：$L[k]\ R[k]$

输出格式如下：

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

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