Count number of distinct elements in submatrix?

Revision en2, by f2lk6wf90d, 2017-12-07 21:06:30

Hello everyone, I thought of this problem yesterday: Given a matrix of length N and width M, answer Q queries of this form:
- x1 y1 x2 y2: Count the number of distinct elements in the submatrix with corners (x1, y1) and (x2, y2).
There is a version of this problem on Codechef, however the bounds for Ai, j are very small. Is there a way to solve this for e.g. Ai, j ≤ 105? I don't have any particular time complexity in mind.

UPD: It turns out that this problem is named "colored orthogonal range counting". It has been solved in "Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization" and "Efficient Colored Orthogonal Range Counting".


  Rev. Lang. By When Δ Comment
en2 English f2lk6wf90d 2017-12-07 21:06:30 462 Solution exists
en1 English f2lk6wf90d 2017-12-06 15:40:37 563 Initial revision (published)