How can we find number of distinct elements in a given submatrix?

Question

Given a N*N matrix and Q queries for the same given matrix. Each Query is of form x1,y1,x2,y2. We have to find the number of distinct elements in the sub-matrix defined by (x1,y1) and (x2,y2) as top left and bottom right corner respectively. Constraints: N<=300 Q<=10^5 I am using naive approach of iterating over the sub matrix for each query. Is there any better approach?

Answer 1

It depends how many queries you can expect, and the number of identical queries you can expect.

One approach is to "memoize" queries, simply to store each query and result, and look that up before doing more serious work.

A more problem-specific approach – probably what your teacher is after – is to compute distinct elements of (0, 0, x, y) for each (right,bottom)=(x,y). Then it's simple set theory to handle each query. But doing the original computation is time consuming.

Remember to add a reference to this SO answer.