Hello everyone!

Today, I have encountered a problem, which can be reduced to this: Given a 2D N * M (1 <= N, M <= 2000) matrix, answer Q (Q <= 5000) queries, each query asks for the number of cells with distinct colors in a submatrix with top left cell (x1, y1) and bottom right cell (x2, y2). (The "static colored orthogonal range counting" problem).

There are no bounds to the number of colors, unlike a well-known Codechef problem.

The 1D problem, SPOJ DQUERY, can be easily solved using a Persistent Segment Tree, with $$$O(n log n)$$$ space and $$$O(log n)$$$ query time.

I have found some papers giving solutions with $$$O(n ^ 2 log ^ 2 n)$$$ preprocessing time and $$$O(log ^ 2 n)$$$ time for each query, however, the data structures there seems to bee too advanced for me. It seems to be an upgrade of the data structure for the 1D problem, but it's something different (and much more complex) than a Persistent Segment Tree.

Are there any simpler algorithms that work in $$$O(n)$$$ or less for each query (which is enough for this problem)? Offline solutions might be good too, but I haven't thought of any (I've tried to use Mo's algorithm, but I don't know how).

Thanks for helping!