Given n ≤ 106 points with integer coordinates on a 2D plane, for each point compute the number of points with coordinates greater than those of the current one.
I can only think of a solution in 
which sorts the points using x coordinate, and then for every point count the number of points after it with greater y coordinate. That can be done by using Fenwick tree or segment tree.
Can we do better than that? Can we do something simpler without using a segment tree or Fenwick tree?
Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).
Auto comment: topic has been updated by nhtrnm (previous revision, new revision, compare).
Compress them and apply sqrt-decomposition? :D
A little bit simpler imo
There's a nice solution for this problem using merge sort. I'm sure it works when all coordinates are distinct, but I think we can generalize it.
When I get home I'll explain it better.
Yeah, this problem can be solved with merge sort which I haven't thought of before: link.
No, you are correct that O(n log n) is the best you can do. The reason is because if you take the special case that all x-coordinates are distinct, then the problem becomes equivalent to inversion counting, which requires at least O(n log n) time.
See here for reason: https://math.stackexchange.com/a/2112513