#87. 策略游戏

策略游戏

题目描述

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

有一个长度为 nn 的数组 AA 和一个长度为 mm 的数组 BB,在此基础上定义一个大小为 n×mn \times m 的矩阵 CC,满足 Cij=Ai×BjC_{i j} = A_i \times B_j。所有下标均从 11 开始。

游戏一共会进行 qq 轮,在每一轮游戏中,会事先给出 44 个参数 l1,r1,l2,r2l_1, r_1, l_2, r_2,满足 1l1r1n1 \le l_1 \le r_1 \le n1l2r2m1 \le l_2 \le r_2 \le m

游戏中,小 L 先选择一个 l1r1l_1 \sim r_1 之间的下标 xx,然后小 Q 选择一个 l2r2l_2 \sim r_2 之间的下标 yy。定义这一轮游戏中二人的得分是 CxyC_{x y}

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

请问:按照二人的最优策略,每轮游戏的得分分别是多少?

输入格式

第一行输入三个正整数 n,m,qn, m, q,分别表示数组 AA,数组 BB 的长度和游戏轮数。

第二行:nn 个整数,表示 AiA_i,分别表示数组 AA 的元素。

第三行:mm 个整数,表示 BiB_i,分别表示数组 BB 的元素。

接下来 qq 行,每行四个正整数,表示这一次游戏的 l1,r1,l2,r2l_1, r_1, l_2, r_2

输出格式

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

3 2 2
0 1 -2
-3 4
1 3 1 2
2 3 2 2
0
4

样例1解释

这组数据中,矩阵 CC 如下:

$$\begin{bmatrix} 0 & 0 \\ -3 & 4 \\ 6 & -8 \end{bmatrix} $$

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

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

6 4 5
3 -1 -2 1 2 0
1 2 -1 -3
1 6 1 4
1 5 1 4
1 4 1 2
2 6 3 4
2 5 2 3
0
-2
3
2
-1

样例3

见选手目录下的 game3.ingame3.ans

样例4

见选手目录下的 game4.ingame4.ans

数据范围

对于所有数据,1n,m,q1051 \le n, m, q \le {10}^5109Ai,Bi109-{10}^9 \le A_i, B_i \le {10}^9。对于每轮游戏而言,1l1r1n1 \le l_1 \le r_1 \le n1l2r2m1 \le l_2 \le r_2 \le m

测试点编号 n,m,qn, m, q \le 特殊条件
11 200200 1, 2
22 1
33 2
454 \sim 5
66 10001000 1, 2
787 \sim 8 1
9109 \sim 10 2
111211 \sim 12
1313 105{10}^5 1, 2
141514 \sim 15 1
161716 \sim 17 2
182018 \sim 20

其中,特殊性质 1 为:保证 Ai,Bi>0A_i, B_i > 0。 特殊性质 2 为:保证对于每轮游戏而言,要么 l1=r1l_1 = r_1,要么 l2=r2l_2 = r_2