RECTQUER - Editorial



Author: Roman Rubanenko
Tester: Gerald Agapov
Editorialist: Jingbo Shang




Prefix sum


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.


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[i][j] = S[i-1][j] + S[i][j-1] – S[i-1][j-1] + Matrix[i][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.


Solutions to be uploaded soon.

Author’s solution can be found here.
Tester’s solution can be found here.


I used 2-D BIT, i would like to know any faster methods

I used 3D matrix and DP strategy :slight_smile:

As it is given that only 10 different colours are used , we can use hashing here

using namespace std;
int main(){
int buff;
int a[301][301];
int dp[301][301][10];
for(int i = 0 ; i <= 300 ; i++){
    for(int j = 0 ; j <= 300 ; j++){
        for(int k = 1 ; k <= 10 ; k++){
            dp[i][j][k] = 0;
int n,q;
for(int i = 1 ; i <= n ; i++){
    for(int j = 1 ; j <= n ; j++){
        dp[i][j][a[i][j]] = 1;
for(int i = 1 ; i <= n ; i++){
    int hash[11] = {0};
    for(int j = 1 ; j <= n ; j++){
        for(int k = 1 ; k <= 10 ; k++){
            dp[i][j][k] = hash[k];
int x1,x2,y1,y2;
if( x1 == x2 && y1 == y2) cout<<1<<endl;
int hash[11] = {0};
int count = 0;
for(int i = x1 ; i <= x2 && count<10; i++){
    for(int j = 1 ; j <= 10 ; j++){
        if(dp[i][y2][j] - dp[i][y1-1][j] > 0 && hash[j] == 0) {
            hash[j] = 1;
            count++ ;
return 0;
1 Like

This is basically same with the method in editorial :slight_smile:


Complexity of my solution is: PreProcessing O(N^2) + Q*Nlog(N). I didn’t understand this editorial and would like to know some better algorithms for this kind of problems.

@yashkumar18 i thought of implementing using segment trees and it actually worked for larger inputs also, (tle). so i thought of another method and came up with an algo similar to the above editorial, Method mentioned in the above editorial is better as you can see here,,sudharkj. I thought of implementing using bit also. But, i was not able to code.
@shangjingbo and @yashkumar18 could any one tell why segment tree method gave tle, but not for bit? Thanks.

1 Like

What is the complexity of above code?

I think it is O(N^2 D) + O(Q N D). It stores 1-D prefix sum for each number and row. For each query, it needs to enumerate all different numbers and rows.

The idea is to maintain 10 different 2-D prefix sum.

1 Like

i think segment tree should give a faster solution but i prefer BIT, its much simpler, but i am not sure why segment tree would give tle

I used 2-d segment tree for each element 1-10.

may be wrong implementation of segment trees because someone else sg1993 was able to do it. Anyhow i liked the method in this editorial.

I solved it using binary search. but it took a bit time, 0.82

my segment tree works well.

how to solve it with binary search?

Do the prefix sum for the binary

What does this mean?

Hi could anyone please help me to find error in my solution for this problem RECTQUER. link to solution:
Algorithm: Instead of 2D array, I have taken n * n one dimensional array.
now one 2D temp array[n*n][10] (it will store cumulative count of all numbers till ith position).
now to get the number of distinct element from (x1,y1) to (x2,y2) , I am converting these index for one dimensional array so l=x1 * n+y1 and r=x2 * n+y2.
then take the difference array[r][10]-array[i][10]. I have also taken care of boundary conditions and everything. please run this program in C++11 for given sample input or user generated input and point out why it is failing…please Help!!!

please tell how to solve with binary search?

I am having problem in understanding the editorial solution. For the matrix given in the question
i.e. {{1, 2, 3}, {3, 2, 1}, {5, 6, 3}} the prefix sum matrix would be {{1, 3, 6}, {4, 8, 12}, {9, 19, 26}}?? If my prefix sum matrix is correct then the answer to the query (2,2) - (3,3) would be s[3][3] - s[3][1] -s[1][3] + s[1][1] = 26-9-6+1 => 12. How come it is 12? when the answer should be 4. Please tell me where I am wrong?