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)".
- $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)".
