3 个条目
区间平均化操作;答案是前缀和点集下凸壳的斜率,用单调栈维护分段平均,交叉相乘避免浮点。
当 Q_(i,j) 含 A(i)B(j) 时,把转移化为点与直线的截距,用下凸壳查询切线;按 X、K、窗口的单调性选择凸壳维护方式。
凸组合、凸包与下凸壳;支撑线和线性函数 Y-KX 的最小值在凸壳顶点取得。