@[WAPER4EVER](/user/72419) 调边界,直接二分可以吗。
by FutaRimeWoawaSete @ 2022-09-27 21:58:18
@[Hakuoro](/user/132533) 什么意思啊/fad
by WAPER4EVER @ 2022-09-27 22:01:24
@[WAPER4EVER](/user/72419) 啊,就像你维护的 k 不具有单调性一样,你在还是维护出来凸包的情况下就只能二分吧。
在单调队列里找到属于这个边界范围内的位置然后二分最优点。
by FutaRimeWoawaSete @ 2022-09-27 22:04:47
套个线段树或者分治一定对!!!
by Itst @ 2022-09-27 22:09:58
emm,我再想亿想
by WAPER4EVER @ 2022-09-27 22:14:57
线段树(好像可以树状数组)套李超树肯定可行,不过应该有更优的解法。
by _cyle_King @ 2022-09-27 22:16:50
@[WAPER4EVER](/user/72419) 小丑了,貌似其实是可以有一个区间都被弹出去的情况。
可能确实得写个分治才是对的。
感觉以线段树举例,对于每个节点维护出来凸包然后在 log 个点上二分,至少这样暂时是可做的。
by FutaRimeWoawaSete @ 2022-09-27 22:20:34
哦对对对,我大概懂了,谢谢大家 ;w;
by WAPER4EVER @ 2022-09-27 22:25:26