题解区的写法里。

都是在整体二分递归函数的每层写一个 $O(n)$ 的循环。

但是这样真的不是 $n^2$ 的吗？

类比线段树，共 $O(n)$ 个点，每个点上跑 $O(n)$。