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, however the bounds for *A*_{i, j} are very small. Is there a way to solve this for e.g. *A*_{i, j} ≤ 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" and "Efficient Colored Orthogonal Range Counting".