@c8b2b9ef

Algorithm's worst case complexity and expected complexity surely can differ. Select kth item is widely regarded as O(n) but worst case will degenerate into O(n^2).

The algorithm complexity is O(n*(logn+m)), here logn is the binary search; m is the loop in collect function, it is hard to determine what m is, but you can refer to following statement:

if n->infinity.

then m->infinity.

But (m/n)->0; (sol's shape will be like a normal distribution, where n is the area, m is just a line)

So m is an existence with smaller degree (not linear) than n. Meaning m!=O(n).

If above is too vague or hard to understand, there is a clear one.

As I stated in the PS, if the inner implementation is BST with sum information instead of arraylist, to find upper layer sum of count with smaller ending value will be done in O(logn), and insert into its own layer BST will be done in O(logn). So the overall complexity will be O(n*(logn+logn)) = O(n*logn).

So I insist my original post is correct.