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.
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.
Tried solving this Problem, using simple 2D Fenwick tree using map<pair<int,int>,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 attempt
OST attempt
Segment Tree AC
You need to use vector with BIT.
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.
Map is slow
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?
Hey, can I see your AC code
Sure, here.
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
Good username.
Agreed.
I think he is your younger brother xD.
A standard problem about the scanline with segment tree