wqs二分里套斜率优化
有两种写法, 在斜率优化的转移和最后答案的处理上有区别
f[i] = f[Q[l]] + m * (pre[i] - pre[Q[l]]) * (pre[i] - pre[Q[l]]) + x;
(f[n] - ans * m) - pre[n] * pre[n]
和
f[i] = f[Q[l]] + (pre[i] - pre[Q[l]]) * (pre[i] - pre[Q[l]]) + x;
m * (f[n] - ans * m) - pre[n] * pre[n]
第一种是错的(0分), 第二种是对的, 但是我觉得第一种应该也对才对啊..
在下面用 ai 代替 prei−preQl
具体: 答案的式子是这样: (m∑ai2)−pren∗pren
第一种在dp时求得 ∑(mai2+x)=m∑ai2+mx 所以最后减掉 mx
第二种在dp时求得 ∑(ai2+x)=∑ai2+mx 所以最后剪掉mx后再乘上m
那为什么第一种是错的?