### DanceTheTragonDrainer's blog

By DanceTheTragonDrainer, history, 5 years ago,

Given N points in 2-D plane and Q queries. In each query you are given a rectangle (aligned with x,y axes) defined by the points x1, y1, x2, y2 where (x1, y1) is the lower left corner and (x2, y2) is the upper right corner, find the number of points inside the rectangle. Points on rectangle are considered inside.

Constraints : 1 ≤ N ≤ 100 000 1 ≤ Q ≤ 100 000 0 ≤ xi, yi ≤ 100 000 0 ≤ x1 < x2 ≤ 100 000 0 ≤ y1 < y2 ≤ 100 000

Does anyone have a link to this question or any implementation.

Thanks. DanceTheTragonDrainer.

 » 5 years ago, # |   +14 Sort points by y coordinate and add them to fenwick tree by x coordinate. In fenwick tree store vectors of y coordinates. To get numbers of points in rectangle [0, x], [0, y] use upper_bound(v.begin(), v.end(), y) — v.begin(). If this is hard to understand use segment tree of segment trees.
•  » » 4 years ago, # ^ |   +3 Tried solving this Problem, using simple 2D Fenwick tree using map,int> as tree. Also with order statistics implementation as given here, but both give TLE. Whereas, using Merge Sort tree gives AC. ( Merge sort tree is basically, a segment tree where each node of tree keeps sorted array of interval it manages. ). Aren't all these supposed to be $O(log^2(N))$ per query? Is there a large constant for BIT and Order Statistics tree? 2D BIT attemptOST attemptSegment Tree AC
•  » » » 4 years ago, # ^ |   0 You need to use vector with BIT.
•  » » » » 4 years ago, # ^ |   0 Okay. But even during the contest yesterday, I searched a lot and found a lot of blogs which said using map in 2d bit only uses $O(log(MaxX)log(MaxY))$ states, so why does it not work as expected? According to my expectations, $Q=10^5,log(10^5)=17$ so total running time should be $289*10^5$ which should easily fit in time limit.
•  » » » » » 4 years ago, # ^ |   0 Map is slow
•  » » » » 4 years ago, # ^ | ← Rev. 5 →   +1 Still gives TLE, here. Anything I might be doing incorrectly?UPD: Nevermind, I forgot that the update I use for bit $x = x + x$&$(-x)$ requires 1 based indexing, and input coordinates can be zero. After fixing indexing, I got an AC. Thanks a lot.As a side note, will this always be faster than a merge sort tree? Atleast for counting points in rectangle?
•  » » » » » 4 years ago, # ^ |   0 Hey, can I see your AC code
•  » » » » » » 4 years ago, # ^ |   0 Sure, here.
•  » » » 4 years ago, # ^ | ← Rev. 4 →   +4 The following is a similar solution based on segment tree of sorted arrays, but the nodes are sorted after adding all the N points, not using Merge Sort during the addition of each point.Segment Tree AC
 » 5 years ago, # |   +32 Good username.
•  » » 5 years ago, # ^ |   +33 Agreed.
•  » » » 5 years ago, # ^ |   +8 I think he is your younger brother xD.
 » 5 years ago, # | ← Rev. 2 →   +8 A standard problem about the scanline with segment tree