[CSP-S 2022] 策略游戏

题目描述:

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

有一个长度为 n 的数组 A 和一个长度为 m 的数组 B，在此基础上定义一个大小为 n×m 的矩阵 C，满足 Cij=Ai×Bj。所有下标均从 1 开始。

游戏一共会进行 q 轮，在每一轮游戏中，会事先给出 4 个参数 l1,r1,l2,r2，满足 1≤l1≤r1≤n、1≤l2≤r2≤m。

游戏中，小 L 先选择一个 l1∼r1 之间的下标 x，然后小 Q 选择一个 l2∼r2 之间的下标 y。定义这一轮游戏中二人的得分是 Cxy。

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

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

输入格式:

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

第二行：n 个整数，表示 Ai，分别表示数组 A 的元素。

第三行：m 个整数，表示 Bi，分别表示数组 B 的元素。

接下来 q 行，每行四个正整数，表示这一次游戏的 l1,r1,l2,r2。

输出格式:

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

输入输出样例:

输入 #1:

输出 #1:

0
4

输入 #2:

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

输出 #2:

说明/提示

【样例解释 #1】

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

在第一轮游戏中，无论小 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≤n,m,q≤10^5，−10^9≤Ai,Bi≤10^9。对于每轮游戏而言，1≤l1≤r1≤n，1≤l2≤r2≤m。

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

其中，特殊性质 1 为：保证 Ai,Bi>0。
特殊性质 2 为：保证对于每轮游戏而言，要么 l1=r1，要么 l2=r2。

思路:

矩阵这个描述就是障眼法。翻译一下题目：

小 L 在 a[l1⋯r1] 中选择一个 x，然后小 Q 在 b[l2⋯r2] 中选择一个 y，分数是 x×y，小 L 想让分数尽可能大，小 Q 想让分数尽可能小。求分数。

也就是说，小 L 掌握主动权，小 L 选择后小 Q 才会从中选择一个数，使 Cxy 尽可能的小，小 L 会从所有可能的 Cxy 中选择最大的哪一个。

我们模拟一下都会出现哪些情况。

小 L 和小 Q 都只能选择正整数，此时小 L 会选择最大的正整数，小 Q 会选择最小的正整数。
小 L 和小 Q 都只能选择负数，此时小 L 会选择最小的负数，小 Q 会选择最大的负数。
小 L 只能选择正整数，小 Q 既能选择正数又能选择负数，此时小 L 会选择最小的正整数，小 Q 会选择最小的负数。
小 L 只能选择负数，小 Q 既能选择正数又能选择负数，此时小 L 会选择最大的负数，小 Q 会选择最大的正整数。
小 L 既能选择正数又能选择负数，小 Q 只能选择正数，此时小 L 会选择最大的正数，小 Q 会选择最小的正数。
小 L 既能选择正数又能选择负数，小 Q 只能选择负数，此时小 L 会选择最小的负数，小 Q 会选择最大的负数。
小 L 既能选择正数又能选择负数，小 Q 也既能选择正数又能选择负数，此时答案会出现不同情况。当小 L 选择正整数时，小 Q 会选择最小的负数；当小 L 选择负数时，小 Q 会选择最大的正数。这种情况下，无论如何选择，结果一定是负数，我们要想让这个负数尽可能地大，那么小 L 在选择数的时候一定要选择绝对值相对较小的数，即小 L 应选择正数中的最小值或负数中的最大值，此时小 Q 选择的数分别为最小的负数与最大的正数，取两种情况的最大值即可。

通过上面的分析，我们发现前 6 种情况都是从两边的最大值和最小值中获得的，只有最后一种情况涉及到了序列 ai 的正数中的最小值和负数中的最大值。

我们在统计答案的时候只需要从两种极值的选择中取最小值最大的情况，然后判断是否存在第 7 中情况，取最大值即可。

至于两个序列的极值的查询，由于不涉及到修改操作，我们可以用 ST 表来维护两个序列的信息。

ST 表预处理复杂度为 O(nlogn+mlogm)，ST 表查询复杂度为 O(1)，总共 q 次查询，所以总时间复杂度为 O(nlogn+mlogm+q)。

完整代码:

#include <bits/stdc++.h>
#define int long long
inline int read() {int x = 0;bool f = true;char ch = getchar();for (; !isdigit(ch); ch = getchar())if (ch == '-')f = false;for (; isdigit(ch); ch = getchar())x = (x << 1) + (x << 3) + ch - '0';return f ? x : (~(x - 1));
}
inline int max(int a, int b) {return a > b ? a : b;
}
inline bool gmx(int &a, int b) {return b > a ? a = b, true : false;
}
inline int min(int a, int b) {return a < b ? a : b;
}const int maxn = (int)1e5 + 5;
const int maxm = (int)1e5 + 5;
const int mlgn = 25;
const int mlgm = 25;int amx[maxn][mlgn], amn[maxn][mlgn], afx[maxn][mlgn], azn[maxn][mlgn];
int bmx[maxm][mlgm], bmn[maxm][mlgm];// 6 个 ST 表
// amx：a 的区间最大值，amn：a 的区间最小值，afx：a 的负数区间最大值，azn：a 的非负数区间最小值。
// bmx：b 的区间最大值，bmn：b 的区间最小值。int lg[maxn];const int maxinf = LONG_LONG_MAX, mininf = LONG_LONG_MIN;signed main() {int n = read(), m = read(), q = read();for (int i = 1; i <= n; ++i) {int x = read();amx[i][0] = amn[i][0] = x;afx[i][0] = (x < 0 ? x : mininf);azn[i][0] = (x >= 0 ? x : maxinf);}for (int i = 1; i <= m; ++i) {int x = read();bmx[i][0] = bmn[i][0] = x;}for (int i = 2; i <= max(n, m); ++i)lg[i] = lg[i >> 1] + 1;for (int j = 1; j <= lg[n]; ++j) {for (int i = 1; i + (1 << j) - 1 <= n; ++i) {int p = i + (1 << (j - 1));amx[i][j] = max(amx[i][j - 1], amx[p][j - 1]);afx[i][j] = max(afx[i][j - 1], afx[p][j - 1]);amn[i][j] = min(amn[i][j - 1], amn[p][j - 1]);azn[i][j] = min(azn[i][j - 1], azn[p][j - 1]);}}for (int j = 1; j <= lg[m]; ++j) {for (int i = 1; i + (1 << j) - 1 <= m; ++i) {int p = i + (1 << (j - 1));bmx[i][j] = max(bmx[i][j - 1], bmx[p][j - 1]);bmn[i][j] = min(bmn[i][j - 1], bmn[p][j - 1]);}}while (q--) {int la = read(), ra = read(), lb = read(), rb = read();int sa = lg[ra - la + 1], sb = lg[rb - lb + 1];int pa = ra - (1 << sa) + 1, pb = rb - (1 << sb) + 1;int amax = max(amx[la][sa], amx[pa][sa]);int amin = min(amn[la][sa], amn[pa][sa]);int afmx = max(afx[la][sa], afx[pa][sa]);int azmn = min(azn[la][sa], azn[pa][sa]);int bmax = max(bmx[lb][sb], bmx[pb][sb]);int bmin = min(bmn[lb][sb], bmn[pb][sb]);int ans = mininf;gmx(ans, amax * (amax >= 0 ? bmin : bmax));gmx(ans, amin * (amin >= 0 ? bmin : bmax));if (afmx != mininf)gmx(ans, afmx * (afmx >= 0 ? bmin : bmax));if (azmn != maxinf)gmx(ans, azmn * (azmn >= 0 ? bmin : bmax));printf("%lld\n", ans);}return 0;
}