Given $n<= \leq 10^6$ 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 $O(n \log n)$ 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?
↵
I can only think of a solution in $O(n \log n)$ 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?
