[Problem] Number of points with coordinates greater than those of the current one

Правка en1, от nhtrnm, 2017-10-02 03:28:48

Given n <  = 106 points 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?

Теги data structures, 2d

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский nhtrnm 2017-10-02 03:30:27 8 Tiny change: 'Given $n<=10^6$ poin' -> 'Given $n \leq 10^6$ poin'
en2 Английский nhtrnm 2017-10-02 03:29:53 25 Tiny change: '6$ points on a 2D ' -> '6$ points with integer coordinates on a 2D '
en1 Английский nhtrnm 2017-10-02 03:28:48 565 Initial revision (published)