Contest Duration: - (local time) (100 minutes) Back to Home

## Ex - Manhattan Christmas Tree Editorial by cai_lw

Given an array of $$N$$ integers in $$[0,S)$$, a wavelet tree can be constructed in $$O(N\log S)$$ and answer online queries that count array elements satisfying $$i\in [l,r), a_i\in[d,u)$$ in $$O(\log S)$$, for any valid $$l, r, d, u$$. This is sometimes called the range_freq operation of the wavelet tree.

Given a set of $$N$$ points in 2D space, after some $$O(N\log N)$$ pre-processing, the range_freq operation of the wavelet tree can be used to count points in any rectangular region in $$O(\log N)$$. First, compress Y coordinates into integers in $$[0,N)$$, while maintaining their relative order. Then, sort points by their X coordinates, and create a wavelet tree from their Y coordinates. (Note that $$S=O(N)$$ with the compressed Y coordinates) Finally, for a rectangular query, binary search the rectangle’s boundaries in the point set’s original X and Y coordinates, to find the corresponding $$l,r,d,u$$ boundaries in the wavelet array.

Thus, for each query in this problem, one can binary search the answer by calling the rectangular point counting subroutine $$O(\log X)$$ times. The overall time complexity is $$O(N\log N+Q\log N \log X)$$.

AC submission (C++, 1563ms): https://atcoder.jp/contests/abc233/submissions/28146443

posted:
last update: