从 ACGO U128722 开始做吧。
这个应该是最弱的斜率优化了。
不知道难度啊，那咋办。
假设 fi 为以 i 结尾的答案。
令 Bi=∑j=1iAj。
fi=j=1mini−1fj+(Bi−Bj)2=j=1mini−1fj+Bi2+Bj2−2BiBj=(j=1mini−1fj+Bj2−2BiBj)+Bi2
即 fi−Bi2=minj=1i−1fj+Bj2−2BiBj。
现在考虑如何查询这个。
注意到这个可以表示成若干条直线 yj=−2Bjx+fj+Bj2，则这个就相当于查询 x=Bi 时 minyj 的值。
显然可以李超线段树动态添加直线做到 O(nlogn)。但是注意到这道题 O(nlogn) 只能拿 0pts，而我问了豆包，这个是 CSP-S 的第二题，和这个同位置的题是 road，road 80pts 是大众分，所以这个 0pts 也是大众分，你如果只会这个你就完蛋了。（（（
所以这个，怎么做。
画个图，就会发现可能是答案的直线一定两两满足 ki>kj,bi>bj。
注意到有个十分好的性质，查询的 x≥0 且单调递增；添加的 Bi 单调递增。所以我们添加直线的 k 值一直在减小。所以我们可以做这样的事：弄个单调队列，对于新加的直线，我们看队列顶的 b 是不是大于直线的 b，如果大于，恭喜它和我被 pipilong2024 一样被单队了。然后记录下这条直线与上一条直线的交点。最后移动当前 x 到新的 x 同时通过交点弹出队尾即可，最后在的那条直线一定是最小值。
这样，我们就做到了严格 O(n)，并没有超过了我 road 的分数。
太晚了，代码明天写。
咦什么叫我用斜率优化切了个红题？
有帮助，赞一个