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