自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 23:11:34，当前版本为作者最后更新于2025-05-07 12:52:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

感觉我的做法理论上是 2log？

首先这个题意是，从 $a$ 和 $b[l,r]$ 选两个可以空的子区间，最大化长度和乘上最小值。

考虑 $b_i$ 作为最小值的极大区间，按这个极大区间和询问区间 $[l,r]$ 的关系分类讨论。极大区间被 $[l,r]$ 包含的情况可以预处理之后做二维数点。预处理考虑分类讨论一下 $b_i$ 和 $a$ 中选的数的大小关系，$b_i$ 较大的情形可以用李超树处理。$[l,r]$ 被极大区间包含的情况类似。

相交也即 $b$ 中选的子区间是个 $[l,r]$ 的前缀或者后缀，这里考虑后缀。$b_i$ 较小的情况还是简单的，考虑从 $m\to 1$ 扫描线，一个被加入的 $b_i$ 的极大区间 $[L,R]$ 的贡献是 $(r-L+1+c_i)b_i$，$c_i$ 表示 $b_i$ 能取到的 $a$ 中的最长区间长度，要求 $L\ge l$ 但不需要要求 $L\le r$，用树状数组套李超树即可，时间 $O(n\log^2 n)$ 空间 $O(n\log n)$。

对于 $b_i$ 较大的情况得去维护每个 $a$ 的答案，也就是对 $a_i$ 排序之后，设 $len_i$ 表示 $a_i$ 对应的极大区间长度，维护一个 $mn_i$ 表示 $a_i$ 能取到的最小的 $b$ 中极大区间的左端点。还是从 $m\to 1$ 扫描线，加入一个 $[L,R]$ 的影响是 $mn$ 的一段前缀取 $\min$。一次询问相当于求 $\max_{mn_i\ge l} a_i(r-mn_i+1+len_i)$。

将取 $\min$ 变成 $O(n)$ 次区间加，也就是维护 $d_i$ 支持区间加，求后缀中 $\max a_i(d_i+r)$。这东西感觉 KTT 不太能维护。一个显然的做法是直接分块维护块内的凸包，$O(n\sqrt {n\log n})$ 或者 $O(n\sqrt n)$，我实现了这个，已经可以过了。但是！因为 $a$ 是有序的，我们维护的是 $(a_i,a_id_i)$ 构成的凸包，给 $d_i$ 加上某个值是不会改变凸包的。所以可以对 $x$ 轴建线段树，套持久化线段树/平衡树维护区间凸包应该就能 $\log^2$ 了。