P11348 [KTSC 2023 R2] 团队建设

**请勿用 C++14 (GCC 9) 提交。** 请在程序开头加入如下代码： ```cpp std::vector build_teams(std::vector A1, std::vector B1, std::vector A2, std::vector B2, std::vector L1, std::vector R1, std::vector L2, std::vector R2); ```

**题目译自 [2023년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2023/) T4 「[팀 만들기](https://assets.ioikorea.kr/ioitst/2023/2/teambuilding/teambuilding_statement.pdf)」** 在 20XX 年的国际信息学奥林匹克竞赛中，新增了一个混合项目。在这个项目中，一名男生和一名女生将组成一个团队来解决问题。为了组建代表队参加混合项目，信息学奥林匹克竞赛委员会选拔了 $N$ 名男生候选人和 $M$ 名女生候选人。每个男生候选人从 $0$ 到 $N-1$ 编号，每个女生候选人从 $0$ 到 $M-1$ 编号。 团队的实力取决于两名学生的思维能力和编程能力。学生的思维能力和编程能力可以用 $1$ 到 $10^9$ 之间的整数表示。第 $i$ 名男生的思维能力是 $A_1[i]$，编程能力是 $B_1[i]$。第 $j$ 名女生的思维能力是 $A_2[j]$，编程能力是 $B_2[j]$。如果第 $i$ 名男生和第 $j$ 名女生组成一个团队，那么这个团队的实力定义为 $\left(A_1[i] + A_2[j]\right) \times \left(B_1[i] + B_2[j]\right)$。 由于所有学生都是经过激烈竞争选拔出来的，因此不存在某个男生在思维能力和编程能力上都优于另一个男生的情况。更具体地说，男生的思维能力随着编号的增加而增加，编程能力随着编号的增加而减少。即，对于 $i$ $(0 \leq i \leq N-2)$，有 $A_1[i] < A_1[i+1]$ 和 $B_1[i] > B_1[i+1]$。女生也是如此，思维能力随着编号的增加而增加，编程能力随着编号的增加而减少。即，对于 $0 \leq j \leq M-2$，有 $A_2[j] < A_2[j+1]$ 和 $B_2[j] > B_2[j+1]$。 信息学奥林匹克竞赛委员会希望根据不同的场景组建实力最强的团队。共有 $Q$ 个场景，每个场景编号从 $0$ 到 $Q-1$。在第 $k$ 个场景中，男生的编号必须在 $L_1[k]$ 到 $R_1[k]$ 之间，女生的编号必须在 $L_2[k]$ 到 $R_2[k]$ 之间。请编写一个程序，计算每个场景中可以组建的团队的最大实力。 你需要实现以下函数： ```cpp vector build_teams(vector A1, vector B1, vector A2, vector B2, vector L1, vector R1, vector L2, vector R2); ``` - `A1, B1`：长度为 $N$ 的数组。第 $i$ $(0 \leq i \leq N-1)$ 名男生的思维能力是 $A1[i]$，编程能力是 $B1[i]$。 - `A2, B2`：长度为 $M$ 的数组。第 $j$ $(0 \leq j \leq M-1)$ 名女生的思维能力是 $A2[j]$，编程能力是 $B2[j]$。 - `L1, R1, L2, R2`：长度为 $Q$ 的数组。在第 $k$ $(0 \leq k \leq Q-1)$ 个场景中，男生的编号必须在 $L1[k]$ 到 $R1[k]$ 之间，女生的编号必须在 $L2[k]$ 到 $R2[k]$ 之间。 - 该函数返回一个长度为 $Q$ 的数组 $C$。$C[k]$ 是第 $k$ 个场景中可以组建的团队的最大实力。 注意，提交的代码中不应包含任何输入输出操作。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N\,M$ - 第 $2+i$ $(0 \leq i \leq N-1)$ 行：$A1[i]\,B1[i]$ - 第 $2+N+j$ $(0 \leq j \leq M-1)$ 行：$A2[j]\,B2[j]$ - 第 $2+N+M$ 行：$Q$ - 第 $3+N+M+k$ $(0 \leq k \leq Q-1)$ 行：$L1[k]\,R1[k]\,L2[k]\,R2[k]$

示例评测程序按以下格式输出： - 第 $1+k$ $(0 \leq k \leq Q-1)$ 行：函数 `build_teams` 返回的数组的第 $k$ 个元素

### 样例 1 解释 考虑 $N=5, M=4, A1=[2,7,8,9,10], B1=[10,9,8,6,1], A2=[1,3,5,9], B2=[10,8,7,5], Q=3, L1=[0,2,1], R1=[4,3,1], L2=[1,0,0], R2=[3,2,0]$ 的情况。 评测程序将调用如下函数： ```cpp build_teams([2,7,8,9,10], [10,9,8,6,1], [1,3,5,9], [10,8,7,5], [0,2,1], [4,3,1], [1,0,0], [3,2,0]); ``` 在第 $0$ 个场景中，男生的编号必须在 $0$ 到 $4$ 之间，女生的编号必须在 $1$ 到 $3$ 之间。选择 $1$ 号男生和 $3$ 号女生组成团队，团队的实力为 $(7+9) \times (9+5) = 224$。这是满足条件的团队中实力最大的。 在第 $1$ 个场景中，男生的编号必须在 $2$ 到 $3$ 之间，女生的编号必须在 $0$ 到 $2$ 之间。选择 $2$ 号男生和 $2$ 号女生组成团队，团队的实力为 $(8+5) \times (8+7) = 195$。这是满足条件的团队中实力最大的。 在第 $2$ 个场景中，男生的编号必须是 $1$，女生的编号必须是 $0$。团队的实力为 $(7+1) \times (9+10) = 152$。 因此，函数应返回 `[224,195,152]`。 ### 样例 2 解释 考虑 $N=4, M=2, A1=[1,6,8,10], B1=[9,5,3,1], A2=[5,6], B2=[8,7], Q=4, L1=[0,1,2,3], R1=[0,1,2,3], L2=[0,0,0,0], R2=[1,1,1,1]$ 的情况。 评测程序将调用如下函数： ```cpp build_teams([1,6,8,10], [9,5,3,1], [5,6], [8,7], [0,1,2,3], [0,1,2,3], [0,0,0,0], [1,1,1,1]); ``` 在第 $0$ 个场景中，选择 $0$ 号男生和 $1$ 号女生组成团队，团队的实力为 $(1+6) \times (9+7) = 112$。 在第 $1$ 个场景中，选择 $1$ 号男生和 $1$ 号女生组成团队，团队的实力为 $(6+6) \times (5+7) = 144$。 在第 $2$ 个场景中，选择 $2$ 号男生和 $0$ 号女生组成团队，团队的实力为 $(8+5) \times (3+8) = 143$。 在第 $3$ 个场景中，选择 $3$ 号男生和 $0$ 号女生组成团队，团队的实力为 $(10+5) \times (1+8) = 135$。 这些都是满足条件的团队中实力最大的。因此，函数应返回 `[112,144,143,135]`。 ### 数据范围 对于所有输入数据，满足： - $1 \leq N \leq 10^5$ - $1 \leq M \leq 10^5$ - 对于每个 $i$ $(0 \leq i \leq N-1)$，$1 \leq A1[i], B1[i] \leq 10^9$ - 对于每个 $j$ $(0 \leq j \leq M-1)$，$1 \leq A2[j], B2[j] \leq 10^9$ - 对于每个 $i$ $(0 \leq i \leq N-2)$，$A1[i] < A1[i+1], B1[i] > B1[i+1]$ - 对于每个 $j$ $(0 \leq j \leq M-2)$，$A2[j] < A2[j+1], B2[j] > B2[j+1]$ - $1 \leq Q \leq 10^5$ - 对于每个 $k$ $(0 \leq k \leq Q-1)$，$0 \leq L1[k] \leq R1[k] \leq N-1$ - 对于每个 $k$ $(0 \leq k \leq Q-1)$，$0 \leq L2[k] \leq R2[k] \leq M-1$ 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $5$ | $N \leq 500, M \leq 500, Q \leq 500$ | | $2$ | $10$ | $Q \leq 20$ | | $3$ | $10$ | 对于每个 $k$ $(0 \leq k \leq Q-1)$，$L2[k]=0, R2[k]=M-1$ | | $4$ | $35$ | 对于每个 $k$ $(0 \leq k \leq Q-1)$，$L2[k]=R2[k]$ | | $5$ | $40$ | 无附加限制 |