写在前面：分治这个东西好像容易被大家忘记，专门找一些题练练

Luogu P1429

分治基本思想，确定一个分割点，各自处理左右两部分答案，最后合并答案

先考虑一维，确定一个中间点，假设左右分别都求出来了最近点对，然后需要求整个部分的答案，需要考虑跨分界点的点对，设 为左右两边答案中小的那个，只需要考虑分界点左右距离为 内的点，至多有两个点，复杂度降到

二维一样，按其中一维像上面做之后，把另一维排序，取靠近分界点的点进行枚举，枚举也无须做到平方级别，每个点只需要尽可能枚举相近的点即可，可以证明点数不超过 个，复杂度降到

LOJ #6490

也是区间分成两半去考虑，当两边的答案处理好之后，需要考虑跨过 的区间

以左边为例，依次枚举左端点 ，求出跨 的长度在 的区间中最大的区间，具体用前缀和 + 表实现 查找，记录下来 再往后扫， 的答案就是 ， 一定是在 记录的最大区间里面的

右边同样，注意开要

本文采用CC-BY-SA-3.0协议，转载请注明出处
作者: wsy_jim