[CSP-S 2022] 策略游戏

GitHub跳转原题关系图返回列表

把极大极小乘积按 B 区间符号分三类讨论，只需在 A 区间查询最值、最小正数、最大负数和是否有零。

OJ: luogu

题目 ID: P8818

难度:提高+/省选-

标签:ST表分类讨论极小化极大思维

创建: 2026-06-21 14:48

更新: 2026-10-01 22:20

形式化题目

给定长度 $n$ 的数组 $A$ 和长度 $m$ 的数组 $B$ ，定义矩阵 $C_{ij} = A_i \times B_j$ 。

每次询问给出 $l_1, r_1, l_2, r_2$ 。小 L 先从 $[l_1, r_1]$ 选一个下标 $x$ ，小 Q 再从 $[l_2, r_2]$ 选一个下标 $y$ ，得分是 $C_{xy}$ 。小 L 想让得分尽量大，小 Q 想让得分尽量小，双方都采用最优策略。

求每次询问的得分。

暴力解法

思路

枚举小 L 选哪个 $x$ ，再枚举小 Q 选哪个 $y$ ，对每个 $x$ 求小 Q 能压到的最小得分，最后取最大值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-21 14:48
 * update_at: 2026-10-01 22:20
 */
// brute.cpp：小数据暴力解，枚举小 L 选哪个 x，再枚举小 Q 选哪个 y，直接按题意做极大极小。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF64 = (1LL << 60); // 哨兵值，比任何真实答案都小/大

int n, m, q;
ll a[205]; // 数组 A，只服务小数据
ll b[205]; // 数组 B，只服务小数据

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        // 外层枚举小 L 的选择 x，内层求小 Q 能压到的最小得分，再取最大
        ll answer = -INF64;
        for (int x = l1; x <= r1; x++) {
            ll worst = INF64;
            for (int y = l2; y <= r2; y++) {
                worst = min(worst, a[x] * b[y]);
            }
            answer = max(answer, worst);
        }
        cout << answer << '\n';
    }

    return 0;
}

复杂度

时间： $O(|A区间| \times |B区间|)$ 每次询问
空间： $O(n + m)$

瓶颈

单次询问就是区间长度的乘积级， $n, m, q \leqslant 10^5$ 时完全不可行。

正解

思路

先固定小 L 选到的一个数 $a$ ，思考小 Q 会怎么选：

如果 $a > 0$ ，为了让乘积尽量小，小 Q 一定会选 $B$ 区间里的最小值；
如果 $a < 0$ ，小 Q 一定会选 $B$ 区间里的最大值；
如果 $a = 0$ ，结果恒为 $0$ 。

所以一轮查询里， $B$ 区间真正有用的信息只有最小值 $\min B$ 和最大值 $\max B$ 。然后按 $B$ 区间的符号分三类讨论。

1. $B$ 区间全非负

正数 $a$ 的得分是 $a \times \min B$
负数 $a$ 的得分是 $a \times \max B$

为了让结果尽量大：

如果 $A$ 区间里有非负数，选最大的 $a$
否则只能在负数里选最接近 $0$ 的那个负数

2. $B$ 区间全非正

正数 $a$ 的得分是 $a \times \min B$ （非正数）
负数 $a$ 的得分是 $a \times \max B$ （非负数）

为了让结果尽量大：

如果 $A$ 区间里有非正数，选最小的那个数（负数绝对值最大，乘积最大）
否则只能选最小正数

3. $B$ 区间同时有正有负

正数 $a$ 会被乘上 $\min B$ ，结果是负数
负数 $a$ 会被乘上 $\max B$ ，结果也是负数
如果 $A$ 区间有 $0$ ，那直接选 $0$ 最优

否则只需要比较：

最小正数 $\times \min B$
最大负数（最接近 $0$ 的负数） $\times \max B$

于是 $A$ 区间里需要查询的量只有：最大值、最小值、最小正数、最大负数、是否存在 $0$ 。这些都可以用 ST 表和前缀和在 $O(1)$ 查询出来； $B$ 区间只要查最小值和最大值即可。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-06-21 14:48
 * update_at: 2026-10-01 22:20
 */
// main.cpp：把极大极小乘积按 B 区间符号分三类讨论，
// 用 ST 表维护 A 区间的最值、最小正数、最大负数、是否有零。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 100005;
const ll INF64 = (1LL << 60); // 哨兵值，表示"不存在"，足够大且乘积不会溢出

int n, m, q;
ll a[MAXN]; // 数组 A
ll b[MAXN]; // 数组 B

int lg2_table[MAXN];  // lg2_table[i]：floor(log2(i))，ST 表查区间时用
int zero_prefix[MAXN]; // zero_prefix[i]：A[1..i] 中 0 的个数前缀和

ll st_a_max[18][MAXN];    // ST 表：A 区间最大值
ll st_a_min[18][MAXN];    // ST 表：A 区间最小值
ll st_a_posmin[18][MAXN]; // ST 表：A 区间最小正数，不存在时为 INF64
ll st_a_negmax[18][MAXN]; // ST 表：A 区间最大的负数（最接近 0），不存在时为 -INF64

ll st_b_max[18][MAXN]; // ST 表：B 区间最大值
ll st_b_min[18][MAXN]; // ST 表：B 区间最小值

// 查询 st 表区间 [l,r] 的最大值
ll query_max(ll st[18][MAXN], int l, int r) {
    int k = lg2_table[r - l + 1];
    return max(st[k][l], st[k][r - (1 << k) + 1]);
}

// 查询 st 表区间 [l,r] 的最小值
ll query_min(ll st[18][MAXN], int l, int r) {
    int k = lg2_table[r - l + 1];
    return min(st[k][l], st[k][r - (1 << k) + 1]);
}

// 预处理 1..limit 的 log2 下取整表
void build_logs(int limit) {
    lg2_table[1] = 0;
    for (int i = 2; i <= limit; i++) {
        lg2_table[i] = lg2_table[i >> 1] + 1;
    }
}

// 预处理 A 的四张 ST 表和零个数前缀和
void build_st_a() {
    for (int i = 1; i <= n; i++) {
        st_a_max[0][i] = a[i];
        st_a_min[0][i] = a[i];
        st_a_posmin[0][i] = (a[i] > 0 ? a[i] : INF64);
        st_a_negmax[0][i] = (a[i] < 0 ? a[i] : -INF64);
        zero_prefix[i] = zero_prefix[i - 1] + (a[i] == 0);
    }

    for (int k = 1; (1 << k) <= n; k++) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 1; i + len - 1 <= n; i++) {
            st_a_max[k][i] = max(st_a_max[k - 1][i], st_a_max[k - 1][i + half]);
            st_a_min[k][i] = min(st_a_min[k - 1][i], st_a_min[k - 1][i + half]);
            st_a_posmin[k][i] = min(st_a_posmin[k - 1][i], st_a_posmin[k - 1][i + half]);
            st_a_negmax[k][i] = max(st_a_negmax[k - 1][i], st_a_negmax[k - 1][i + half]);
        }
    }
}

// 预处理 B 的两张 ST 表
void build_st_b() {
    for (int i = 1; i <= m; i++) {
        st_b_max[0][i] = b[i];
        st_b_min[0][i] = b[i];
    }

    for (int k = 1; (1 << k) <= m; k++) {
        int len = 1 << k;
        int half = len >> 1;
        for (int i = 1; i + len - 1 <= m; i++) {
            st_b_max[k][i] = max(st_b_max[k - 1][i], st_b_max[k - 1][i + half]);
            st_b_min[k][i] = min(st_b_min[k - 1][i], st_b_min[k - 1][i + half]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    build_logs(max(n, m));
    build_st_a();
    build_st_b();

    while (q--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;

        // B 区间只关心最小值和最大值
        ll b_min = query_min(st_b_min, l2, r2);
        ll b_max = query_max(st_b_max, l2, r2);

        // A 区间需要的五类信息
        ll a_max = query_max(st_a_max, l1, r1);
        ll a_min = query_min(st_a_min, l1, r1);
        ll a_posmin = query_min(st_a_posmin, l1, r1);
        ll a_negmax = query_max(st_a_negmax, l1, r1);
        bool has_zero = (zero_prefix[r1] - zero_prefix[l1 - 1] > 0);

        ll answer;

        if (b_min >= 0) {
            // B 区间全非负，小 Q 会取最小的 B。
            if (a_max < 0) {
                answer = a_negmax * b_max;
            }
            else {
                answer = a_max * b_min;
            }
        }
        else if (b_max <= 0) {
            // B 区间全非正，小 Q 会取最大的 B。
            if (a_min > 0) {
                answer = a_posmin * b_min;
            }
            else {
                answer = a_min * b_max;
            }
        }
        else {
            // B 区间同时有正有负。
            if (has_zero) {
                answer = 0;
            }
            else if (a_max < 0) {
                answer = a_negmax * b_max;
            }
            else if (a_min > 0) {
                answer = a_posmin * b_min;
            }
            else {
                // A 有正有负：最小正数乘 b_min、最大负数乘 b_max 取较大者
                ll cand1 = a_posmin * b_min;
                ll cand2 = a_negmax * b_max;
                answer = max(cand1, cand2);
            }
        }

        cout << answer << '\n';
    }

    return 0;
}

复杂度

预处理 ST 表： $O((n+m)\log(n+m))$
每次查询： $O(1)$

总时间复杂度 $O((n+m+q)\log(n+m))$ ，空间复杂度 $O((n+m)\log(n+m))$ 。

总结

这题本质不是矩阵博弈，而是：

先把"对手会怎么选"压缩成符号分类；
再把每种情况需要的区间信息整理成固定几个最值；
用 ST 表把这些区间最值做到 $O(1)$ 查询。

最关键的是把极大极小问题拆成清楚的分类讨论。

图示解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P8818 [CSP-S 2022] 策略游戏

题目描述

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

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

游戏一共会进行 $q$ 轮，在每一轮游戏中，会事先给出 $4$ 个参数 $l_1, r_1, l_2, r_2$ ，满足 $1 \le l_1 \le r_1 \le n$ 、 $1 \le l_2 \le r_2 \le 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 在最优策略下的得分。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
20
4

输入输出样例 #2

输入 #2

text

1
2
3
4
5
6
7
86 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

text

说明/提示

【样例解释 #1】

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

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

在第一轮游戏中，无论小 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 \le n, m, q \le {10}^5$ ， $-{10}^9 \le A_i, B_i \le {10}^9$ 。对于每轮游戏而言， $1 \le l_1 \le r_1 \le n$ ， $1 \le l_2 \le r_2 \le m$ 。

测试点编号	$n, m, q \le$	特殊条件
$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$ 。

[CSP-S 2022] 策略游戏

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

1. BBB 区间全非负

2. BBB 区间全非正

3. BBB 区间同时有正有负

代码

复杂度

总结

图示解析

1. $B$ 区间全非负

2. $B$ 区间全非正

3. $B$ 区间同时有正有负