我把 bzoj 的数据下载到本地测,过了,但是交 bzoj 的时候莫名其妙地有一个询问答案应该是 0 但是变成了 49,进行了不重要的一些写法的更换之后变成了 51,猜测是 UB,但是交到洛谷上面的时候发现 WA 50,错了 #8-#13, #15, #16, #18, #20 这几个点,觉得可能是什么地方写错了,故来求助这份代码哪里错了。
思路不是通常做这题的李超树做法,而是用了 EI 论文里面的做法,即
维
护块 Lj 为其中包含的 2j 个函数的上包络线所组成的分段。每当加入一个函数的时候,如
果存在两个包含同样多个函数的块,我们就将其合并,通过原来两块各自的分段计算出合
并后的分段。
由于朴素实现还没有调对,所以没有实现 Fractional Cascading。
如果有人帮我找找 UB 或者指出我代码里面的错误,我会十分感谢的。
代码:https://www.luogu.com.cn/paste/1zaskw6t
P.S. bzoj 的数据里面含有 ∣S∣>105 的非法数据(如第一个点的 Project -211631.23831 9.51754
),不知道洛谷的数据有没有?