Count number of distinct elements in submatrix

Revision en1, by TrungNT, 2020-11-23 18:24:11

Hello everyone!

Today, I have encountered a problem, which can be reduced to this: Given a 2D N * M (1 <= N, M <= 2000) matrix, answer Q (Q <= 5000) queries, each query asks for the number of cells with distinct colors in a submatrix with top left cell (x1, y1) and bottom right cell (x2, y2). (The "static colored orthogonal range counting" problem).

There are no bounds to the number of colors, unlike a well-known Codechef problem.

The 1D problem, SPOJ DQUERY, can be easily solved using a Persistent Segment Tree, with $$$O(n log n)$$$ space and $$$O(log n)$$$ query time.

I have found some papers giving solutions with $$$O(n ^ 2 log ^ 2 n)$$$ preprocessing time and $$$O(log ^ 2 n)$$$ time for each query, however, the data structures there seems to bee too advanced for me. It seems to be an upgrade of the data structure for the 1D problem, but it's something different (and much more complex) than a Persistent Segment Tree.

Are there any simpler algorithms that work in $$$O(n)$$$ or less for each query (which is enough for this problem)? Offline solutions might be good too, but I haven't thought of any (I've tried to use Mo's algorithm, but I don't know how).

Thanks for helping!

Tags 2d, ranges, counting, data structures

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English TrungNT 2020-11-23 18:35:56 1 Tiny change: 'eems to bee too adva' -> 'eems to be too adva'
en2 English TrungNT 2020-11-23 18:29:19 37 Tiny change: 'n a 2D $N * M$ $(1 <=' -> 'n a 2D $N \times M$ $(1 <='
en1 English TrungNT 2020-11-23 18:24:11 1479 Initial revision (published)