Count number of distinct elements in submatrix?
Difference between en1 and en2, changed 462 character(s)
Hello everyone, I thought of this problem yesterday: Given a matrix of length N and width M, answer Q queries of this form:  ↵
- $x_1$ $y_1$ $x_2$ $y_2$: Count the number of distinct elements in the submatrix with corners $(x_1, y_1)$ and $(x_2, y_2)$.  ↵
There is a version of [this problem on Codechef](https://www.codechef.com/DEC13/problems/RECTQUER), however the bounds for $A_{i,j}$ are very small. Is there a way to solve this for e.g. $A_{i,j} \leq 10^5$? 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](https://www.semanticscholar.org/paper/Further-Results-on-Generalized-Intersection-Search-Gupta-Janardan/51e7a5a64c8cacbdfbe6c7b2e735107142232fa6)" and "[Efficient Colored Orthogonal Range Counting](http://www.math.tau.ac.il/~michas/colorbox.pdf)".

History

 
 
 
 
Revisions
 
 
  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)