EasonCookie197's blog

Could someone explain their approach to ABC 233 problem H/Ex
By EasonCookie197, 3 years ago, In English

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:

  1. Binary indexed tree (Fenwick Tree) + offline queries

  2. Some sort of segment tree -ish thing + online queries

I would really appreciate if someone could kindly explain a solution^_^

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Some sort of segment tree -ish thing + online queries

https://www.geeksforgeeks.org/persistent-segment-tree-set-1-introduction/

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply