具体来说，这种做法是将直径端点分成两部分。对于直径长度为奇数，直径中点将所有直径分成了多个部分的情况就任意分成两个部分；新增点接在直径端点上时，额外检查其所在部分的其余点能否被放到另一部分，以保证正确性。

我当时做这题时好像会证复杂度了，但是我现在写博客的时候又感觉不太对。

有没有人能给个证明啊。

我现在认为复杂度里可能是有 $\sqrt m$ 的。

因为我可以构造这样的东西。

中点 1。L: 2。R: 3, 4, 5, 6, 7。

中点 7。L: 2, 3, 4, 5, 6。R: 9。

3, 4, 5, 6 发生转移。

假如 11 被分到了 L，我们就可以添加 11 -> 12 使得 2, 3, 4, 5, 6 再次转移。

这个构造可以继续进行下去，如果程序每次都进行了较劣的决策，应该确实可以达到 $m\sqrt m$。

然而实际上这样的数据不好构造，因为无法控制新的点被放在哪一侧。