### PROBLEM LINK:

**Author:** Roman Rubanenko

**Tester:** Gerald Agapov

**Editorialist:** Jingbo Shang

### DIFFICULTY:

Easy

### PREREQUISITES:

Prefix sum

### PROBLEM:

Given a N*N matrix of at most 10 different numbers, answer Q queries about how many distinct numbers are there in a given sub matrix.

### EXPLANATION:

It is worth noting that there are at most 10 different numbers. Assume they are 1, 2, 3, … , 10.

To answer the number of distinct numbers, we can divide this problem to 10 separate problems:

```
for d = 1 to 10:
Is there any d in the sub matrix?
```

Let’s focus on a given number d. Then the matrix can be treated as binary, i.e. whether the entry equals d. Do the prefix sum for the binary matrix:

```
S*[j] = S[i-1][j] + S*[j-1] – S[i-1][j-1] + Matrix*[j]
```

With this O(N^2) preprocess, we can answer the problem “Is there any d in the sub matrix?” in O(1) time. That is,

```
# of number d in (x1,y1)-(x2,y2) = S[x2][y2]–S[x2][y1-1]–S[x1-1][y2]+S[x1-1][y1-1]
```

Also, you can see the following figure for visualization. Denote the sum of red region as R, similar to Y(ellow), G(ray), B(lue).

Then we can have

```
S[x2][y2] = R + B + G + Y
S[x2][y1-1] = G + B
S[x1-1][y2] = G + Y;
S[x1-1][y1-1] = G
Our goal is R.
```

Using this technique, it is easy to solve this problem in O(N^2 + Q * D). D is the different numbers in the matrix.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Solutions to be uploaded soon.

Author’s solution can be found here.

Tester’s solution can be found here.