8868

· · 个人记录

之前那版题解太乱了，重新理一遍。

即多组询问求

\sum_{[p,q]\subseteq[l,r]}(\max_{j\in[p,q]}a_j)(\max_{j\in[p,q]}b_j)

我们计算出每个 b_j 支配的最大区间 [l_j,r_j]，使得其为最大值；这个单调栈即可解决。

考虑一个 b_j 对询问的 [l,r] 的贡献；显然 j\in[l,r]。

b_j\sum_{\max\{l_j,l\}\le x\le j\le y\le\min\{r_j,r\}}\max_{x\le k\le y}a_k

我们对贡献的区间分四类讨论统计；即下标中谁取到最值。

\textbf{Case 1: }l<l_j,r>r_j b_j\sum_{l_j\le x\le j\le y\le r_j}\max_{x\le k\le y}a_k

考虑预处理，然后对单组询问直接扫描线二维数点统计。

怎么预处理？

\sum_{l\le x\le j\le y\le r}\max_{x\le k\le y}a_k \\=\sum_{l\le x\le y\le r}\max_{x\le k\le y}a_k -\sum_{j+1\le x\le y\le r}\max_{x\le k\le y}a_k-\sum_{l\le x\le y\le j-1}\max_{x\le k\le y}a_k

于是就差分成了三个子问题，解法如下：

我们考虑若干轮查询 \sum_{[x,y]\subseteq[l,r]}\max_{x\le k\le y}a_k 怎么做；也即 loj2051。

考虑对 r 扫描线，在线段树上每个位置 p 维护 \sum_{p\le y\le r}\max_{p\le k\le y}a_k 的信息。

考虑使用一次函数形式，把其描述成 r\max_{p\le k\le r}a_k+C 的形式。

假设 a_t=\max_{p\le k\le r}a_k，则我们在 t 处对一段被严格覆盖区间的 C 直接进行更新即可。

容易用两个 BIT 维护，复杂度 O((n+q)\log n)。

\textbf{Case 2: }l\ge l_j,r\le r_j b_j\sum_{l\le x\le j\le y\le r}\max_{x\le k\le y}a_k

容易发现这样的 b 存在且唯一；其为区间内最大的 b。

继续使用上一类情况的做法即可。

\textbf{Case 3: }l<l_j,r\le r_j b_j\sum_{l_j\le x\le j\le y\le r}\max_{x\le k\le y}a_k \\=b_j\sum_{l_j\le x\le j,x\le y\le r}\max_{x\le k\le y}a_k -b_j\sum_{l_j\le x\le y\le j-1}\max_{x\le k\le y}a_k

第二部分和 \textbf{Case 1} 一样，我们考虑第一部分。

b_j\sum_{l_j\le x\le j,x\le y\le r}\max_{x\le k\le y}a_k \\=\sum_{l_j\le x\le j}b_j\sum_{x\le y\le r}\max_{x\le k\le y}a_k

容易发现，当 r 固定时，每个 x 会被唯一的 b_j 支配。

仍然考虑扫描线，则其与之前问题的区别仅在于，我们同时要维护每个位置所乘的系数 b_j，并且要频繁地替换这个系数。

不妨使用带永久化标记的线段树解决，由于时刻各标记不交，因此直接记录所乘的系数即可。

注意为了还原原状态，还要记录如果不乘上 b 标记，其的权值。

\textbf{Case 4: }l\ge l_j,r>r_j

翻转一下即是 \textbf{Case 3}，略。

综上，我们就在 O(n\log n) 的时间内解决了本题。（认为 n,q 同阶）

由于要计算多种贡献，常数会很大，代码会很长。

指针式代码实现。

数组式代码实现。（可以松过 UOJ）