本文记号可能稍显凌乱，但都能在题面或者前文中找到定义。
部分分
$\text{20 pts}$ – $n,Q\leq 3000$
考虑枚举所有 $\newcommand\bigO{\operatorname{O}}\bigO(n^2)$ 个区间，预先计算它们本身的答案。记
$$\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\end{aligned}$$
则做前缀和 $s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i)$，对于询问 $[\text{ql},\text{qr}]$ 只需回答 $\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr})$ 即可。
令 $n, Q$ 同阶，时空复杂度 $\bigO(n^2)$。 （更多…）