题解：P11949 [KTSC 2025] 木筏制作 / raft

critnos · 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 了。