RT,这玩意有复杂度证明吗？

关于kdt大部分人认为的模板题k远点对学长说kdt是假解，就像问一下有没有个严谨的证明。

虽然我认为这玩意大概是下限就是O（n）