ARC063D Snuke's Coloring 2

题意 ： 平面上有一个左下角坐标 右上角坐标 的矩形，起初长方形内部被涂白。

现在给定 个点，你每次在以下 种操作中选择一种：

• 将矩形内 的区域涂黑

• 将矩形内 的区域涂黑

• 将矩形内 的区域涂黑

• 将矩形内 的区域涂黑

不难发现，最后剩下的白色部分是一个矩形，最大化该矩形的周长。

，时限 。

---

题意不难转化为：求一个周长最大的矩形，使得内部没有特殊点。

考虑分治，每次处理经过 的矩形。

对于某个给定的 的区间，矩形的高是容易确定的，只需要得到两侧距离的 即可。

进一步对 进行分治，当处理跨越 的贡献时，根据单调性不难做到线性。

（具体地，需要双指针和单调队列）

两个分治嵌套，复杂度为 。

不难发现， 的矩形总是能够被选出的。

于是，作为最优答案的矩形必然经过 或者 ，否则周长比不过上面两个。

这样，两次分治即可做到 。