考场花了一张 A4 的草稿纸在这题上面……还导致 T4 没时间调了。
你要是想看我 T4 挂的多惨可以去看 T4 题解。
不难发现其实就是给一个 \(a_1,a_2,...,a_n\) 和一个 \(b_1,b_2,...,b_m\)，然后有一个 \(n\times m\) 的矩阵，\(c_{ij}=a_ib_j\)，每次给定 \(l_1,r_1,l_2,r_2\)，然后求一个 \(x\in[l_1,r_1]\)，使得 \(\min \limits_{j=l_2}^{r_2}\{c_{xj}\}\) 最大。
这东西一眼看上去直接数据结构不太可做，考虑大力分类讨论。
1. 小 L 没有 \(\ge 0\) 的数
那么小 L 一定会拿一个负数出来。
- 如果小 Q 有 \(\ge 0\) 的数，那么小 L 肯定是取 \(a_{l_1},...,a_{r_1}\) 的最大值使得这个值的绝对值尽可能小，而小 Q 一定是把 \(b_j\) 往死里取最大值，那么是 \(maxL\times maxQ\)。
- 如果小 Q 没有 \(\ge 0\) 的，那么答案一定 \(\ge 0\)，那小 L 肯定就取最小使得这个值的绝对值尽可能大，小 Q 肯定取最大，使得这个值的绝对值尽可能小，那么是 \(minL\times maxQ\)。
2. 小 L 只有 \(\ge 0\) 的数
注意是“只有”，说明小 L 只能取一个自然数出来。
- 如果小 Q 有负数，那么小 Q 一定是取最小的负数，为了让答案不那么小，小 L 肯定也取最小的自然数，答案为 \(minQ\times minL\)
- 如果小 Q 也只有 \(\ge 0\) 的数，答案一定 \(\ge 0\)，那么小 L 取最大，小 Q 取最小，答案为 \(maxL\times minQ\)。
3. 小 L 有 \(\ge 0\) 的数与 \(< 0\) 的数
- 如果小 Q 只有 \(\ge0\) 的数，小 L 肯定选最大的自然数，小 Q 只能选最小的了，答案为 \(maxL\times minQ\)。
- 如果小 Q 没有 \(\ge 0\) 的数，小 L 为了令得答案最大，那么肯定选一个绝对值最大的负数，即最小值，小 Q 为了令答案最小，一定取一个绝对值最小的负数，即最大值，答案为 \(minL\times maxQ\)。
- 如果小 Q 既有 \(\ge 0\) 也有 \(<0\) 的数：如果小 L 没有 \(0\)，那么小 L 取正数时，小 Q 必定取负数；小 L 取负数时，小 Q 必定取正数。由于答案的正负性都和小 L 选的数相反或为 \(0\)，那么小 L 一定是尝试取绝对值最小的正/负数，再次分类讨论取最大值即可。如果小 L 有 \(0\)，由于小 L 不选 \(0\) 时答案的正负性一定和小 L 选的数相反或为 \(0\)，那还不如直接选 \(0\)，答案为 \(0\)。
至此，我们讨论完了所有的情况，使用 \(6\) 个 st 表维护 L 的最小值、L 的最大值、L 最大的负数、L 最小的正数、Q 的最小值、Q 的最大值即可。