因为这个错误调了一年,弘文了/ll/ll/ll
考虑如何处理 wqs 二分三点共线的情况,可能对于一般的题目我们会记录一个二元组 (val,cnt)(val,cnt)(val,cnt),即先取 valvalval 较小的,valvalval 相同取 cntcntcnt 较小的,但是在本题中应当取 cntcntcnt 较大的。
因为我们考虑真实值是 val−d⋅cntval-d\cdot cntval−d⋅cnt(ddd 是我们二分的斜率),如果我们取 cntcntcnt 较小的,我们就会判断得到这个斜率的 dp 取值是 >X>X>X 的,然而我们取 cntcntcnt 最大的则能保留这条斜率(这才是正确的!!!)。