Hello everyone, I thought of this problem yesterday: Given a matrix of length N and width M, answer Q queries of this form:
- x₁ y₁ x₂ y₂: Count the number of distinct elements in the submatrix with corners (x₁, y₁) and (x₂, y₂).
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⁵? I don't have any particular time complexity in mind.