s02274. CSP-S 2022 复赛 T2 策略游戏

题目描述

时间限制：1s　内存限制：512MB　来源：洛谷 P8818

题目描述

小 L 和小 Q 在玩一个策略游戏。

有一个长度为 $n$ 的数组 $A$ 和一个长度为 $m$ 的数组 $B$ ，在此基础上定义一个大小为 $n \times m$ 的矩阵 $C$ ，满足 $C_{ij} = A_{i} \times B_{j}$ 。所有下标均从 $1$ 开始。

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_{1}, r_{1}, l_{2}, r_{2}$ ，满足 $1 \leq l_{1} \leq r_{1} \leq n$ 、 $1 \leq l_{2} \leq r_{2} \leq m$ 。

游戏中，小 L 先选择一个 $l_{1} \sim r_{1}$ 之间的下标 $x$ ，然后小 Q 选择一个 $l_{2} \sim r_{2}$ 之间的下标 $y$ 。定义这一轮游戏中二人的得分是 $C_{x y}$ 。

小 L 的目标是使得这个得分尽可能大，小 Q 的目标是使得这个得分尽可能小。同时两人都是足够聪明的玩家，每次都会采用最优的策略。

请问：按照二人的最优策略，每轮游戏的得分分别是多少？

输入格式

第一行输入三个正整数 $n, m, q$ ，分别表示数组 $A$ ，数组 $B$ 的长度和游戏轮数。

第二行： $n$ 个整数，表示 $A_{i}$ ，分别表示数组 $A$ 的元素。

第三行： $m$ 个整数，表示 $B_{i}$ ，分别表示数组 $B$ 的元素。

接下来 $q$ 行，每行四个正整数，表示这一次游戏的 $l_{1}, r_{1}, l_{2}, r_{2}$ 。

输出格式

输出共 $q$ 行，每行一个整数，分别表示每一轮游戏中，小 L 和小 Q 在最优策略下的得分。

样例

输入

输出

0
4

说明/提示

【样例解释 #1】

这组数据中，矩阵 $C$ 如下：

0 - 3 6 04 - 8

在第一轮游戏中，无论小 L 选取的是 $x = 2$ 还是 $x = 3$ ，小 Q 都有办法选择某个 $y$ 使得最终的得分为负数。因此小 L 选择 $x = 1$ 是最优的，因为这样得分一定为 $0$ 。

而在第二轮游戏中，由于小 L 可以选 $x = 2$ ，小 Q 只能选 $y = 2$ ，如此得分为 $4$ 。

【样例 #3】

见附件中的 game/game3.in 与 game/game3.ans。

【样例 #4】

见附件中的 game/game4.in 与 game/game4.ans。

【数据范围】

对于所有数据， $1 \leq n, m, q \leq 10^{5}$ ， $- 10^{9} \leq A_{i}, B_{i} \leq 10^{9}$ 。对于每轮游戏而言， $1 \leq l_{1} \leq r_{1} \leq n$ ， $1 \leq l_{2} \leq r_{2} \leq m$ 。

测试点编号	$n, m, q \leq$	特殊条件
$1$	$200$	1, 2
$2$	$200$	1
$3$	$200$	2
$4 \sim 5$	$200$	无
$6$	$1000$	1, 2
$7 \sim 8$	$1000$	1
$9 \sim 10$	$1000$	2
$11 \sim 12$	$1000$	无
$13$	$10^{5}$	1, 2
$14 \sim 15$	$10^{5}$	1
$16 \sim 17$	$10^{5}$	2
$18 \sim 20$	$10^{5}$	无

其中，特殊性质 1 为：保证 $A_{i}, B_{i} > 0$ 。
特殊性质 2 为：保证对于每轮游戏而言，要么 $l_{1} = r_{1}$ ，要么 $l_{2} = r_{2}$ 。

题面与配图转载自洛谷，内容版权归 CCF 及命题原作者所有。

s02274. CSP-S 2022 复赛 T2 策略游戏 未做

题目描述

题目描述

输入格式

输出格式

样例

说明/提示

s02274. CSP-S 2022 复赛 T2 策略游戏未做