题解：P8818 [CSP-S 2022] 策略游戏

2huk · 2024-09-06 08:39:25 · 题解

题意

小 L 和小 Q 绝顶聪明。

给定长度为 n 的 a 和长度为 m 的 b。q 次询问，给定 l_1,r_1,l_2,r_2。小 L 要选择一个 x \in [l_1, r_1]，小 Q 要选择一个 y \in [l_2,r_2]。小 L 希望最大化 a_x \times b_y，小 Q 希望最小化 a_x \times b_y。求最后的 a_x \times b_y。

做法

小 L 希望最大化。若令 f(x) 表示当小 L 选择 x 时，小 Q 最小能将得分变成多少。即 f(x) = \min_y a_x \times b_y。那么答案为 \max f(x)。

有负数很恶心。分类讨论一下，发现如果两人都绝顶聪明的话，它们所选择的数一定数区间：

• 最大值
• 最小值
• 最大负数（如果存在）
• 最小负数（如果存在）

所以一次询问可以将复杂度从 n^2 优化至 4^2。

维护这四个值是基础 ST 表。