# RECTQUER - Editorial

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

Easy

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[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.

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

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

7 Likes

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

I used 3D matrix and DP strategy

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

``````#include<vector>
#include<algorithm>
#include<iostream>
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;
cin>>n;
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
cin>>a[i][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++){
hash[a[i][j]]++;
for(int k = 1 ; k <= 10 ; k++){
dp[i][j][k] = hash[k];
}}}
cin>>q;
int x1,x2,y1,y2;
while(q--){
cin>>x1>>y1>>x2>>y2;
if( x1 == x2 && y1 == y2) cout<<1<<endl;
else{
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++ ;
}
}}
cout<<count<<endl;
}
}
return 0;
}``````
1 Like

This is basically same with the method in editorial

2 Likes

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, http://www.codechef.com/viewsolution/3069222 (tle). so i thought of another method and came up with an algo similar to the above editorial, http://www.codechef.com/viewplaintext/3095118. Method mentioned in the above editorial is better as you can see here, http://www.codechef.com/DEC13/status/RECTQUER,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
matrix:

What does this mean?