简单分治求助
查看原帖
简单分治求助
302509
zghtyarecrenj楼主2021/6/12 19:30

我把 bzoj 的数据下载到本地测,过了,但是交 bzoj 的时候莫名其妙地有一个询问答案应该是 0 但是变成了 49,进行了不重要的一些写法的更换之后变成了 51,猜测是 UB,但是交到洛谷上面的时候发现 WA 50,错了 #8-#13, #15, #16, #18, #20 这几个点,觉得可能是什么地方写错了,故来求助这份代码哪里错了。

思路不是通常做这题的李超树做法,而是用了 EI 论文里面的做法,即

维 护块 LjL_j 为其中包含的 2j2^j 个函数的上包络线所组成的分段。每当加入一个函数的时候,如 果存在两个包含同样多个函数的块,我们就将其合并,通过原来两块各自的分段计算出合 并后的分段。

由于朴素实现还没有调对,所以没有实现 Fractional Cascading。

如果有人帮我找找 UB 或者指出我代码里面的错误,我会十分感谢的。

代码:https://www.luogu.com.cn/paste/1zaskw6t

P.S. bzoj 的数据里面含有 S>105|S| > 10^5 的非法数据(如第一个点的 Project -211631.23831 9.51754),不知道洛谷的数据有没有?

2021/6/12 19:30
加载中...