### ak3899's blog

By ak3899, history, 6 months ago, ,

i have stuck on this spoj problem in which i have to calculate dominance of points e.g. a point (x1, y1) is said to be dominating another point (x2, y2) if x1>=x2 and y1>=y2 .

https://www.spoj.com/problems/DCEPC705/

my question is that how can i calculate this using binary index tree? this question was queued under the Binary index tree on a portal.

 » 6 months ago, # |   0 First, make coordinate compression to have 0 ≤ x, y < n. Now sort the points in increasing order of x (order points with equal x in increasing order of y). For any point the number of points, which are dominated by it, is equal to count of points behind current point in the list, whose y coordinate is not greater than y coordinate of current point. So iterate over sorted list and keep a binary indexed tree, which counts the number of points with given y coordinate. The number of points, which are dominated by i-th point, is equal to sum(0, yi), after getting the answer for i-th point add 1 at position i of the tree.
 » 6 months ago, # | ← Rev. 3 →   0 There are problem 961E - Туфурама and good tutorial for it