题解：P11587 [KTSC 2022 R2] 编程测试
lsj2009
·
·
题解
来自 https://flamire.blog.uoj.ac/blog/9830 的该题询问 1log 做法。
二分答案 x，使用 Hall 定理判定，限制为 \forall l\le l'\le r'\le r 满足：
x(r'-l'+1)\le b_{l'-1}+\sum\limits_{l'\le i\le r'} a_i+b_i
移下项答案可以刻画为 \min\frac{A_j-B_i}{j-i} 的形式。上猫树，答案的 (i,j) 可能位于 mid 同一侧或两侧：
-
对于位于同一侧的情况预处理每个前缀/后缀的答案，二分答案 x，仅需查询一个 \min {B_i-ix}，李超树即可；此处复杂度 \mathcal{O}(n\log^2{n})。
-
对于位于 mid 两侧的情况，令 c_i=|i-mid|，A_i,B_i 也都和 A_{mid}/B_{mid} 作差（即都变为与 mid 的偏移距离，此步不是必需的，但使得两侧维护东西一致），询问为 \frac{A_i+B_j}{c_i+c_j}，同样二分答案，仅需判断是否有 (A_i-c_ix)+(B_j-c_jx)\ge 0，两侧建可持久化李超树，分别求前缀最值即可，复杂度 \mathcal{O}(q\log^2{n})。
- 先重新描述下问题：给定下凸壳 $F_1(x),F_2(x)$，且均递减，要求找到最大的 $x$ 使得 $F_1(x)+F_2(x)\ge 0$。
- 维护区间 $[l_1,r_1],[l_2,r_2]$（仅都分别考虑两个凸壳上断点，即先二分到 $x$ 分别位于两个凸壳上的所属线段，然后再在内部进行二分就无需二分定位在哪条线段上），取出 $mid_1,mid_2$，不妨设 $mid_1<mid_2$，则若 $F_1(mid_1)+F_2(mid_2)< 0$ 则必有 $x<mid_2$，令 $r_2\gets mid_2$；否则 $x>mid_1$，令 $l_1\gets mid_1$。如此即可在 $\log{n}$ 复杂度内完成双凸包二分。
但问题在于对凸包可持久化还得多付出一个 $\log$。建出凸包直线入栈/弹栈的版本树，则当前凸包可以刻画为一个点在版本树上的到根链上所有点对应直线，对其重剖，可以先双指针定位到 $x$ 所属重链，然后在重链上二分即可。复杂度 $\mathcal{O}(n\log^2{n}+q\log{n})$。