bzoj2961 共点圆 bzoj 4140

时间:2024-01-19 17:32:16

题解:

比较水的一道题

首先我们化简一下式子发现是维护xxo+yyo的最值

显然是用凸包来做

我们可以直接用支持插入删除的凸包 也是nlogn的

因为没有强制在线,我们也可以cdq,考虑前面一半对答案的影响,再考虑后面的

时间复杂度nlog^2n

后面这道强制在线当然可以直接平衡树维护

但是有一种神奇的方法叫做二进制分组

也是比较好理解的

就是在不断重构

时间复杂度 nlog^3n

注意一下,运用cdq分治和二进制分组的前提是

修改操作互不影响

代码: