看到网上的题解基本都是 $O(n \log ^2 n)$ 的，我来说一个 $O(n\log n)$ 的。因为这东西比较平凡所以我不打算放博客里。

相比原来的整体二分多了一个对原数组的排序。在把区间放进数组里面的时候就拆成 $[1,r]-[1,l-1]$（负号可以压在一个 word 里）。这部分也要按 $[1,k]$ 的 $k$ 排序。这样在整体二分求有多少个数在区间 $[l,r]$ 中的时候就可以直接指针扫描过去然后相减了~