idy居然会开1d-1d这个坑ovo之前听讲的时候也只是觉得很神奇,没有真正手写过,所以不明觉厉.
这个东西需要实际问题实际分析.总的思路就是利用决策的单调性.
对于这题,设f(x)=sqrt(x-j)+a[j].那么显然它是凸的.然后若干个它还可以拼成一个奇怪的凸壳状的分段函数.然后我们要取每段的极值.怎么有种半平面交的变形的感觉.
然后发现每次插入的函数的j单增,既x单增.于是只需要开一个双端出的队列就好了.然后每次二分一下两个函数的交的x坐标.其它时候可以完全单调性搞定.
然后算的时候用double会方便很多.
似乎很有意思啊hhh