Link to problem : https://atcoder.jp/contests/abc233/tasks/abc233_h
I have read the editorial, and now I understand that we have to find the number of points that are inside a square area. We could use 2d prefix sums if the coordinates are small. However, the coordinates can be very large ($$$2\times 10^5\times 2 \times 10^5$$$), and that will lead to MLE.
Also, I have read some submissions, and most of them use one of the following solutions:
Binary indexed tree (Fenwick Tree) + offline queries
Some sort of segment tree -ish thing + online queries
I would really appreciate if someone could kindly explain a solution^_^
https://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/
I constructed a segment tree on the $$$x$$$-coordinates of the points. In the node corresponding to the range $$$[l, r)$$$, I stored the $$$y$$$-coordinate of all the points with $$$x \in [l, r)$$$ in a sorted order.
Now to find the number of points inside $$$[l, r) \times [d, u)$$$, simply do a binary search inside each node of the segment tree contained in $$$[l, r)$$$.
Each segment tree query takes $$$O(\log N \log X)$$$ time, giving a $$$O(Q \log^2 X \log N)$$$. Here's my sumbission.
You can see more stuff using this idea here. Some also call it merge-sort tree.
Thanks for your explanation!!